arrays - 如何在 m 排序数组中找到一个元素，其中数组的其余部分为零且未给出 m

Question

给定一个包含 n 个元素的数组。数组中的前 m 个元素已排序(没有重复)并且不为零。 数组的其余部分为零。

需要注意的是m是未知的 - 可以是任何东西，但众所周知 n >> m .

现在，给定 x;如果它存在于数组中，我应该返回它的索引，否则，它不存在。
现在的事情是我必须找到一个算法来做到这一点 .

一个简单的答案是只要下一个元素不为零就扫描数组，时间复杂度为 O(m)，或者只是“二进制搜索”的修改版本，时间复杂度为 O(logn)。
除了这两个解决方案 - 我不知道。 已经暗示我们可以在 O(log m) 时间复杂度中找到 x，通过在 O(logm) 时间内找到 m 然后我可以对前 m 个元素进行二分搜索......但否则我不知道!

Answer 1

您可以找到 m在 O(log m)时间如下(考虑到第一个 m 元素不包含 0 )。

i = 1
while A[i] != 0 do
  i = 2*i
return i

这为您提供了 m 的上限即最多 2m (意思是 m <= i <= 2m )。您所要做的就是对 i 进行二分查找。要查找的数组的第一个元素 x .

每个操作都可以在 O(log m)中完成时间，所以总复杂度是 O(log m) .