Skip to content

Instantly share code, notes, and snippets.

@amgando
Created April 22, 2014 21:45
Show Gist options
  • Save amgando/898c425b75f2fd521b5d to your computer and use it in GitHub Desktop.
Save amgando/898c425b75f2fd521b5d to your computer and use it in GitHub Desktop.
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)
$ 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment