binary_search.rb

class Window
  SCALE = 100

  class Collapsed < ArgumentError; end

  attr_reader :low, :mid, :high, :max

  def set(window)
    # p "setting window to #{window}"
    @low, @mid, @high = window
    self
  end

  def init(size)
    self.set [0, size / 2, size-1]
  end

  def lowside!
    self.set [low, (low+mid)/2, mid-1]
  end

  def highside!
    self.set [mid + 1, (mid+high)/2, high]
  end

  def empty?
    low.nil? && mid.nil? && high.nil?
  end

  def collapsing?
    low == mid || mid == high || low == high
  end

  def data
    [low, mid, high]
  end
  alias_method :inspect, :data

  def scale
    @max ||= high
    self.data.map{ |el| ((el.to_f / @max) * SCALE).to_i }
  end

  def render(line = ' ', target = nil)
    markers = ['\\', '|', '/']
    line_symbol = line

    show = line_symbol * SCALE

    self.scale.each_with_index do |data, idx|
      show[data] = markers[idx]
    end

    show[target] = '*' unless target.nil?

    show
  end

  alias_method :to_s, :render
end


def binary_search(needle, haystack, window = Window.new)

  if window.empty?
    window.init(haystack.length)
  end

  puts window

  low, mid, high = window.data

  if window.collapsing?
    # scan the entire window for the needle

    (window.data.min..window.data.max).each do |idx|
      return idx if needle == haystack[idx]
    end

    # http://devblog.avdi.org/2014/05/21/jim-weirich-on-exceptions/
    fail Window::Collapsed, "failed to find [#{needle}]!"
  end


  # found it
  if needle == haystack[mid]
    return mid

  # now search low side
  elsif needle < haystack[mid]
    return binary_search(needle, haystack, window.lowside!)

  # now search high side
  elsif needle > haystack[mid]
    return binary_search(needle, haystack, window.highside!)
  end
end

# --------------------------------------------------------

SAMPLE_SIZE = 10000
COLLECTION_SIZE = 1000

h = (1..SAMPLE_SIZE).to_a.sample(COLLECTION_SIZE).sort
n = h.sample

# puts "haystack:\n#{h}\n\n"
puts "needle: #{n}\n"
puts "should find it at [#{h.index(n)}]"
puts "looking for #{n}.  found it at #{binary_search(n, h)}"

sample_output.txt

$ ruby binary_search.rb
needle: 4440
should find it at [443]
\                                                 |                                                 /
\                        |                       /
                         \           |           /
                                     \     |     /
                                           \  |  /
                                           \ |/
                                           \|/
                                           \/
                                            /
looking for 4440.  found it at 443

Sherif Abushadi ~/Documents/code/dbc/phase-1/binary-search
$ ruby binary_search.rb
needle: 8029
should find it at [816]
\                                                 |                                                 /
                                                  \                       |                         /
                                                                           \           |            /
                                                                           \     |     /
                                                                                 \  |  /
                                                                                 \| /
                                                                                 \/
                                                                                 /
looking for 8029.  found it at 816

Sherif Abushadi ~/Documents/code/dbc/phase-1/binary-search
$ ruby binary_search.rb
needle: 1180
should find it at [120]
\                                                 |                                                 /
\                        |                       /
\           |           /
\     |     /
      \  |  /
         \| /
          \|/
           \/
looking for 1180.  found it at 120