binary_search.rb

class NumberNotFoundError < ArgumentError; end

def render(points, length)
  puts "_" * length
  display = " " * length
  markers = %w[\\ | /]
  points.each_with_index do |p, idx|
    display[p] = markers[idx]
  end
  puts "%#{length + 5}s  %3s : %3s : %3s" % [display, *points]
end

# binary search requires a sorted set of data
# in fact, quite often we're sorting just so that we can do a binary search!
def binary_search(target, data, markers = [0, (data.length/2), data.length])
  low, mid, high = markers
  render(markers, data.length)

  return mid if data[mid] == target
  raise NumberNotFoundError if low == mid or mid == high

  if data[mid] > target
    markers = [low, (low + mid) / 2, mid]

  elsif data[mid] < target
    markers = [mid, (mid + high) / 2, high]
  end

  sleep(0.1)
  binary_search(target, data, markers)

end

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


data = (1..1000).to_a.shuffle[1..100]
haystack, needle = data.sort, data.sample

# run your simplest posssble tests first!
# p binary_search([1], 1)  # can i find an element in a single element array? (see line 19)
# p binary_search([0], 1)  # what happens if i can't find the element? (see line 20)

puts "looking for #{needle}"# in \n#{haystack}"
p binary_search(needle, haystack)

sample_output.txt

$ ruby binary_search.rb
looking for 15
____________________________________________________________________________________________________
    \                                                 |                                                 /    0 :  50 : 100
____________________________________________________________________________________________________
     \                        |                        /                                                     0 :  25 :  50
____________________________________________________________________________________________________
     \           |            /                                                                              0 :  12 :  25
____________________________________________________________________________________________________
     \     |     /                                                                                           0 :   6 :  12
____________________________________________________________________________________________________
     \  |  /                                                                                                 0 :   3 :   6
____________________________________________________________________________________________________
     \| /                                                                                                    0 :   1 :   3
____________________________________________________________________________________________________
      \|/                                                                                                    1 :   2 :   3
2



$ ruby binary_search.rb
looking for 221
____________________________________________________________________________________________________
    \                                                 |                                                 /    0 :  50 : 100
____________________________________________________________________________________________________
     \                        |                        /                                                     0 :  25 :  50
____________________________________________________________________________________________________
     \           |            /                                                                              0 :  12 :  25
____________________________________________________________________________________________________
                 \     |      /                                                                             12 :  18 :  25
____________________________________________________________________________________________________
                       \  |   /                                                                             18 :  21 :  25
21