algorithm - 给定一个具有不同值的预排序数组，找到满足 A[i]=i 的 x

Question

问题:

令 A 为大小为 n 的整数数组，其中 A[1] < A[2] < ... < A[n] .

(请注意，每个条目可以是正整数或负整数。)

1. 给出一个采用O(log n)的算法是时候找到一个 i这样 A[i] = i , 提供这样一个 i存在。如果没有i存在，算法返回 0 .
2. 证明任何使用比较来解决这个问题的算法都需要时间 Ω(log n) .

到目前为止，我只能找到一种算法，该算法采用 O(n)时间，这很容易，但我知道只有树结构才能O(log n) .
我是算法新手。

提前致谢。

Answer 1

考虑有一些 i其中 a[i] > i然后对于任何 j > i => a[j] > j来自声明A[1] < A[2] < ... < A[n].

也适用于任何 i其中 a[i] < i , 对于任何 j < i => a[j] < j出于同样的原因将成立。

因此，我们可以在这里使用二分查找。 (对于选定的点 p 如果 a[p] > p 然后继续左边的部分，如果 a[p] < p 然后继续右边的部分)