在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).这种情况符合您提到的所有标准.现在,找到零所在位置的问题不能在子O(n)时间内解决.因此,在O(logn)时间内无法解决您的问题.