arrays - 在 O(lgn) 中搜索部分排序的数组

Question

我很难解决这个问题。

A[1..n] is an array of real numbers which is partially sorted:
There are some p,q  (1 <= p <= q <=n) so:
A[1] <= ... <= A[p]
A[p] >= ... >= A[q]
A[q] <= ... <= A[n]

How can we find a value in this array in O(lgn)?
(You can assume that the value exists in the array)

Answer 1

进行 3 次二进制搜索:从 1 到 p，p 到 q 和 q 到 n。复杂度仍然是 O(logn)。

因为我们不知道 p 和 q:

您无法在登录时间内解决此问题。假设您有一个排序的正数列表，其中混有一个零(p+1=q 和 A[q]=0)。这种情况满足你提到的所有标准。现在，无法在 sub O(n) 时间内解决找到零所在位置的问题。因此您的问题无法在 O(logn) 时间内解决。