Find maximum element in sorted arrays in logarithmic time

Question

Been stuck on this for a while, would really appreciate some help:

Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right. For example, [35,42,5,15,27,29] is a sorted array that has been circularly shifted k = 2 positions, while [27,29,35,42,5,15] has been shifted k = 4 positions. Give an algorithm for finding the maximum element in A that runs in O(log n) time.

The elements in A are distinct.

---

I understand that to achieve O(log n) time I'll probably have to search through the list by starting at the middle, and then going left or right, then splitting the list in half over and over, but I'm not sure how to attack it beyond that.

Answer 1

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.

Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.

However, if you assume the elements are distinct, then you can indeed give an $O(\log n)$ time algorithm.

Assume the array was sorted ascending. Once it is cyclic shifted, we will have that, in the rotated array (say $a[1,2, \dots n]$), that $a[1] \gt a[n]$. (It might help to draw a figure here, plotting $i$ on x-axis and $a[i]$ on the y-axis).

Now if you pick a $j$, you compare $a[j]$ with $a[1]$ and move right or left, depending on whether it is greater or lesser, like binary search.

Answer 2

A cyclic shift is just an offset transformation in the array. That is, if $k$ is known, you can define the virtual sorted array $A'$ by

$\qquad\displaystyle A'[i] = A[(i+k) \bmod n]$

You can use standard binary seach on $A'$, that is replace every array access to element $i$ in the search algorithm by an access to $(i+k) \bmod n$.

The same works for any (computable and) known permutation of an array.

Answer 3

Here is one way of finding the max:

Let left and right be the extreme elements of the array.

Start at the middle element whose index is e
If A[e] is smaller than the elements surrounding it
    return max(A[e-1], A[e+1])
Else
    If right > left
        Recursively search in right sub-array (A[e] included)
    Else
        Recursively search in left sub-array (A[e] included)

Answer 4

the image contain all the answer that how the complexity can be o(long).

Answer 5

I think we could do the follow first, choose the middle number which is 5 and then compere it with the lift term in your case it is 35. If the middle < left then we can eliminate the right part of the array which is [5,15,25,29].

this is the idea but it needs to add some conditions to be more efficient.

Thanks @Baghdadi