pandaman - 4 months ago 6x

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

Source (Stackoverflow)

Comments