如果值可能不在数组中，如何编写二进制搜索方法

Question

如果我要查找的值可能不在数组中，我将如何编写二进制搜索方法？

二分查找：

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

如果值在数组中，效果很好。

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

但如果不是，则出现错误。

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

stack level too deep (SystemStackError

我有两个大的字符串数组（每个字符串在其自己的数组中都是唯一的），但数组之间存在重叠，这正是我试图找到的。我需要修改该方法，使其在找不到特定字符串时不会使脚本崩溃，然后继续迭代。

您可以想象每个字符串看起来都类似于 akbvuxef。虽然这应该无关紧要。

Answer 1

如果您试图找到 2 个数组的重叠部分，请使用设置交集运算符：

[1, 2, 3] & [2, 3, 4]
 => [2, 3]

Answer 2

这是作业吗？如果没有，那么只需使用 Array#bsearch.

如果是家庭作业，那么考虑一下当你没有更多的值可以测试时会发生什么；您的 to 将 <= 您的 from （也就是说，您的搜索大小 space 为空 - 没有更多值可供测试）。如果发生这种情况，您应该引发异常或 return 一些被解释为 "value not found".

的值

如果值可能不在数组中，如何编写二进制搜索方法

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

ruby

binary-search