如何在一个m有序数组中查找元素，在这个数组的其余部分都是零且m未知。

Question

给定一个有n个元素的数组。数组中前m个元素已按升序排序（无重复项）且不为零。数组的其余部分为零。

应注意m未知 - 它可能是任何值，但已知n远大于m。

现在，如果x存在于数组中，则应返回其索引，否则它不存在。现在问题是，我必须找到一种能够实现此目的的算法。

扫描数组直到下一个元素不是零，时间复杂度为O(m)；或者使用“二分查找”的修改版本，时间复杂度为O(logn)，这两种方法都是微不足道的答案。除此之外我没有头绪。我们可以通过在O(log m)的时间内找到m来在前m个元素上进行二分查找，然后在O(logm)的时间内找到x，这一点已经被提出了提示。

- prism

---

你的想法是正确的。在前 m 个元素中进行二分查找是正确的方法。 - m.raynal

'm' 是未知的 @m.raynal，这是问题。 - User_67128

Answer 1

您可以按照如下步骤在O(log m)的时间内找到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)。

- m.raynal