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

Question

假设已经给出了一个数组并且想要在该数组中找到元素,那么如何使用二进制搜索搜索该数组中的元素,并且给定的数组已经排序并且数组的大小未知.可以应用线性搜索,但我试图找出比线性算法更快的搜索.

Answer 1

如果您可以测试是否已超出数组范围,则可以使用修改后的二进制搜索(假设基于1的数组):

1. lower = 1,upper = 1;
2. while(A [upper] <element)upper*= 2;
3. 正常二进制搜索(下,上).

否则,没有真正的方法可以做到这一点:假设你发现某个地方等于你需要的元素,你不知道它是否已经脱离了数组.