pandaman pandaman - 2 years ago 68
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".

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download