问题如下：
假设您得到了一个非常大的整数数组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（假设从左到右以降序排列）。
到目前为止，我想到的方法是：
使用for循环从索引0迭代到包含第一个0的索引，然后与k比较。这需要O（n）时间，因此不符合时间限制。
对A本身进行二进制搜索。这需要O（log 1,000,000,000）时间并且超过了时间限制。
我有点被困在这里，无法想到任何其他方法。
在最坏情况下O（logn）运行的方法是什么？
嗨，这种方法是基于修改后的二进制搜索
如果匹配返回则从第一个索引开始
将索引加倍，直到找到值或结束为止
a）如果值大于k，则继续
b）否则，如果值小于k BinarySearch（index / 2，index，k）
因此，基本上，我们要做的就是向前跳来缩小搜索空间，就像nice_dev的先前答案一样；但是在跳跃时，我们还检查了我们的值是否在特定窗口中，如果是，则停止跳跃并在最后一个窗口中进行二进制搜索
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句