在 1,000,000,000 个元素中搜索键的算法，其中键位于前 n 个索引中，而无需事先指定 n

Question

问题如下：

假设给定一个非常大的整数数组 A，其中包含 1,000,000,000 个元素，元素按降序排序。然而，只有前n个元素包含正整数数据，但n的值未知。数组的其余元素包含零。

给出 search(A,k) 方法的算法，用于在数组 A 中搜索键 k。它返回找到 k 的数组的索引，否则返回 -1。您的算法必须在最坏情况下运行 O(logn) 时间。

您可以使用 binarySearch(A, k, left, right) 在 A[left] 到 A[right] 中搜索 k（假设从左到右按降序排序）。

到目前为止我想到的方法：

1. 使用 for 循环从索引 0 迭代直到包含第一个 0 的索引并与 k 进行比较。这需要 O(n) 时间，因此不符合时间限制。

2. 对 A 本身进行二分查找。这需要 O(log 1,000,000,000) 时间并且超出了时间限制。

我有点被困在这里，无法想到任何其他方法。

在最坏情况下运行 O(logn) 的方法是什么？

Answer 1

您好，这种方法基于修改后的二分搜索

1. 如果匹配则从第一个索引开始返回

2. 将索引加倍，直到找到值或结束

   a) 如果 Value 大于 k 则继续

   b) 否则如果值小于 k BinarySearch(index/2, index, k)

所以基本上我们所做的是通过向前跳跃来缩小我们的搜索空间，就像nice_dev之前的回答一样；但是在跳跃时，我们还检查我们的值是否在特定窗口中，如果是，我们停止跳跃并对最后一个窗口进行二分搜索