Skip to content

Instantly share code, notes, and snippets.

@astronomy88

astronomy88/binary_search.rb

Last active August 29, 2015 14:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save astronomy88/11184994 to your computer and use it in GitHub Desktop.
Save astronomy88/11184994 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
binary_search.rb
def binary_search x, low = 0, high = -1
#-- Assume that a is already sorted
a = [3, 5, 7, 8, 10, 11, 14, 15, 26, 33, 34, 36, 39, 40, 41, 44, 45, 48, 49]
high = a.length - 1 if high == -1
midpoint = (high + low) / 2
if low == midpoint
return -1
elsif x < a[midpoint]
high = midpoint
binary_search(x, low, high)
elsif x > a[midpoint]
low = midpoint
binary_search(x, low, high)
else
return x
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment