5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ So $k$ is known? $\endgroup$ – Raphael Apr 25 '13 at 7:38
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Aryabhata, thanks for your response. You're right that the elements need to be distinct, I forgot to mention that. I'm still having trouble understanding the answer. In the example [35,42,5,15,27,29], let's say I started at the middle, 5. Comparing against 15, I decide to move right because that's the direction where it's increasing. Ultimately I won't end up at 42. What am I doing wrong? $\endgroup$ – user2317714 Apr 25 '13 at 0:26
  • $\begingroup$ Never mind, I just understood what you're proposing, thanks a lot! $\endgroup$ – user2317714 Apr 25 '13 at 1:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $k$ is known, the maximum element can be found in $O(1)$ time. We don't need binary search. $\endgroup$ – Aryabhata Apr 25 '13 at 15:49
  • $\begingroup$ @Aryabhata Ah, my bad, I answered "How to find some element in a shifted sorted array?". That's probably why I could not make sense of your answer. Thanks! $\endgroup$ – Raphael Apr 25 '13 at 16:04
  • $\begingroup$ Yeah, finding the maximum helps find $k$, and then we can use your answer to do an arbitrary binary search. (But there are direct ways too, without having to find $k$). $\endgroup$ – Aryabhata Apr 25 '13 at 16:06
1
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ Very good! I derived the same solution $\endgroup$ – dukevin Nov 12 '16 at 3:51
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This idea is already given, in much more detail, in the accepted answer. Welcome, but please only post answers if you have something new to add. $\endgroup$ – David Richerby Sep 4 '15 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.