假设给定了一个数组并想在该数组中查找元素,您如何使用二进制搜索在该数组中搜索元素,并且给定的数组已经排序并且数组的大小未知。 可以应用线性搜索,但我正在尝试找出比线性算法更快的搜索。
最佳答案
如果你可以测试你是否落在数组范围之外,那么你可以使用修改后的二进制搜索(假设从 1 开始的数组):
- 下限 = 1,上限 = 1;
- while (A[upper] < element) upper *= 2;
- 正常二分搜索(下,上)。
否则,没有真正的方法可以做到这一点:假设您在某个地方找到了与您需要的元素相等的东西,您无法知道它是否已经从数组中掉落。
关于algorithm - 未知大小数组的二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16513429/