题目如下:
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).
目前想到的方法:
使用 for 循环从索引 0 迭代到包含第一个 0 的索引，然后与 k 进行比较。这需要 O(n) 时间，因此不符合时间限制。
对 A 本身进行二分查找。这需要 O(log 1,000,000,000) 时间并且超过了时间限制。
我有点卡在这里，想不出任何其他方法。
在最坏情况下 O(logn) 运行的方法是什么？
最佳答案
您好，此方法基于修改后的二分查找
如果匹配返回则从第一个索引开始
将索引加倍直到找到值或结束
a) 如果 Value 大于 k 继续
b) 否则如果值小于 k BinarySearch(index/2, index, k)
所以基本上我们所做的就是通过向前跳来缩小我们的搜索空间，就像 nice_dev 之前的回答一样；但是在跳转时我们还检查我们的值是否在特定窗口中，如果是我们停止跳转并二进制搜索最后一个窗口
关于在 1,000,000,000 个元素中搜索一个键的算法，该键位于前 n 个索引中，而没有事先指定 n，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64131856/