在 1,000,000,000 个元素中搜索一个键的算法，该键位于前 n 个索引中，而没有事先指定 n

Question

题目如下:

Suppose you are given a very large integer array A with 1,000,000,000 elements, with elements sorted in descending order. However, only the first n elements contain data which are positive integers, but the value of n is unknown. The rest of the array elements contain zeroes.

Give the algorithm for a method search(A,k) to search for a key k in the array A. It returns the index of the array where k is found, or -1 otherwise. Your algorithm must run in worst case O(logn) time.

You may use binarySearch(A, k, left, right) that searches for k in A[left] through A[right] (assuming left to right is sorted in descending order).

目前想到的方法:

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 之前的回答一样；但是在跳转时我们还检查我们的值是否在特定窗口中，如果是我们停止跳转并二进制搜索最后一个窗口