algorithm - 未知大小数组的二进制搜索

Question

假设给定了一个数组并想在该数组中查找元素，您如何使用二进制搜索在该数组中搜索元素，并且给定的数组已经排序并且数组的大小未知。可以应用线性搜索，但我正在尝试找出比线性算法更快的搜索。

Answer 1

如果你可以测试你是否落在数组范围之外，那么你可以使用修改后的二进制搜索(假设从 1 开始的数组):

1. 下限 = 1，上限 = 1；
2. while (A[upper] < element) upper *= 2;
3. 正常二分搜索(下，上)。

否则，没有真正的方法可以做到这一点:假设您在某个地方找到了与您需要的元素相等的东西，您无法知道它是否已经从数组中掉落。