Question

Consider a variant of the array in previous problem. An array A[1..n] has a property that it first rises monotonically up to some point i then it monotonically decreases until some point j and then rises again. That is A[k] < A[k + 1] for all k ∈ [1..i−1]∪[j..n−1] and A[k] > A[k + 1] if i ≤ k < j. Can we still find i in O(logn) time? If not what is the minimum time required?

Answer 1

We cannot find i in O(logn) time. Consider the below scenarios.

Let's say we have array A [1,2,3,4,5,4,3,2,1,2,3,4,5]

Now in above array we first find the middle element which is 7th(3). We can analyze(compare with adjacent) that this middle sequence is decreasing so now we will consider only left sub array because i will be present there.

Again we will find middle and compare with adjacent elements and figure out whether it is increasing or decreasing. If increasing then we will consider right sub array and if decreasing then left sub array. Repeat steps till the middle element is i (when its left and right both elements are smaller). So, in this case we can findout solution in o(logn).

Now consider array A [1,2,3,4,5,6,7,8,4,3,5,6,7]

In above array middle element is 7th (7). Now when we compare it with adjacent elements we see it is increasing but we don't know which increasing sequence it is : first or last. So, we can not decide which sub array left or right we should consider to search i.

So, we cannot solve it with binary search. The best possible way to search with linear search in o(i) time.