pandaman pandaman - 1 year ago 60
Ruby Question

How to write a binary search method if value might not be in array

How would I write a binary search method if the value I'm looking for might not be in the array?

Binary search:

def binary_search(array, value, from=0, to=nil)
to = array.count - 1 unless to
mid = (from + to) / 2

if value < array[mid]
return binary_search(array, value, from, mid - 1)
elsif value > array[mid]
return binary_search(array, value, mid + 1, to)
return mid

It works great if the value is in the array.

binary_search([1,2,3,5], 5)

But if its not, there is an error.

binary_search([1,2,3,5], 4)

stack level too deep (SystemStackError

I have two large arrays of strings (each string is unique in its own array), but there is overlap across the arrays which is what I'm trying to find. I need to modify the method so it won't crash the script if it doesn't find a specific string, and then continues iterating.

You could imagine each string looks similar to
. Though that shouldn't matter.

Answer Source

Is this homework? If not, then just use Array#bsearch.

If it is homework, then consider what happens when you reach the point that you have no more values to test; your to will be <= your from (that is, the size of your search space is empty - there are no more values left to test). In the case that happens, you should raise an exception or return some value which is interpreted as "value not found".