Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Binary Search
# Taking on the Binary Search challenge
# http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
class Array
# Binary search; assumes array is sorted
# If value is found in the array, it returns an index where it can be found.
# If the value occurs multiple times in the array, it will just return the
# first place it is found (not necessarily the first occurrence in the array).
# If the value is not found, it returns nil.
def bsearch(value)
return nil if self.length == 0
range = (0..self.length - 1)
while range.last >= range.first
mid = (range.last - range.first) / 2 + range.first
case self.at(mid) <=> value
when 0 # values are equal
return mid
when 1 # mid is greater
range = (range.first..mid-1)
when -1 # value is greater
range = (mid+1..range.last)
end
end
return nil
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment