时间戳

首页 > 解决方案 > 用于在 1,000,000,000 个元素中搜索键的算法，其中键位于前 n 个索引中，而不事先指定 n

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

问题描述

问题如下：

假设给定一个非常大的整数数组 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) 下运行的方法是什么？

标签： algorithmtime-complexity

解决方案

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

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

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

    a) 如果值大于 k 继续

    b) else if value 小于 k BinarySearch(index/2, index, k)

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

推荐阅读