pandaman - 10 months ago 31

Ruby Question

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)

else

return mid

end

end

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

`akbvuxef`

Answer

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".