4

Possible Duplicate:
Searching a number in a rotated sorted Array

I have a sorted array and it has been right rotated N times, where N is unknown. Now I want to do a binary search on it. How can it be done?

eg initial array 1 4 5 8 15

now roted N=1 time   15  1  4  5  8
N= 2                  8 15  1  4  5

N can have any value, and can be greater than the number of elements.

Community
  • 1
  • 1
algorithmX
  • 91
  • 1
  • 1
  • 6
  • why on earth would you do such a thing? – jakev Feb 06 '11 at 05:30
  • 1
    Maybe its an interview question. A naive and inefficient way is to just resort the array again and perform the binary search haha – Enrique Feb 06 '11 at 05:32
  • If elements can repeat, you cannot do better than Omega(n) in the worst case. Consider an array of all zeroes, except one, which is one. –  Feb 06 '11 at 06:19
  • This is not an exact duplicate. That linked possible question talks about searching for a known number; whereas this talks about finding the position of the minimum value which is unknown. – lprsd May 17 '12 at 13:18
  • You can possibly find the 2 transition points, which divides the array into 3 sorted arrays. Then do binary search on all 3 arrays to find the element you're looking for. To find the transition points, simply do binary search until you have 2 elements left, and one of them is either < or > than k. k can be an arbitrary number in the array such as the midpoint. O(log n) is required to find the transition pts, and O(log n) required to do BS on all 3 subarrays. – Henley Jul 30 '13 at 21:04

1 Answers1

2

Short answer is, you don't (at least, not on the entire array at once). This is because binary search requires the elements to be sorted in order to work.

About the best you can do is search each half of the array separately using binary search. For example, to continue your example above, if N = 2 your array becomes 8 15 1 4 5. The 8 15 and the 1 4 5 are still sorted, and so you can binary search each of those sub-arrays. In the general sense, the algorithm therefore becomes:

Let your array be A, its length be M, and the target value be T.
If (N is 0 or a multiple of M)
    Binary search A for T
Else
    The sub-array A1 is the first (M mod N) elements of A.
    The sub-array A2 is the remaining (M - (M mod N)) elements of A.
    If (the first element of A <= T)
        Binary search A1 for T
    Else
        Binary search A2 for T

The reason you can restrict your search to either A1 or A2 based on the first element of A is because if A[0] > T, then all elements of A1 will also be > T by definition, and therefore T cannot be in A1.

HTH!

EDIT As Chris points out in the comments following, there is a much simpler approach than this that does in fact allow you to continue performing a binary search on the entire array. While the above would work, his approach ingeniously performs a similar function but over the entire array by using a modified comparison operation.

Mac
  • 14,615
  • 9
  • 62
  • 80
  • 3
    Your first paragraph is wrong. The key insight is that if you have a sorted array and you rotate it, the result is a sorted array with a different comparison function. Specifically, the comparison is `x` is less than `y` iff `(x < y) || (x > A[0] && y < A[0])`. You can then do a binary search using this comparison. – Chris Hopman Feb 06 '11 at 06:16
  • @Chris: that makes sense. I'd never have thought of it that way - that it is still sorted, just under a different definition. That's a real eye opener. – Mac Feb 06 '11 at 06:27
  • Both Chris' solution and this one don't work if elements are allowed to repeat. –  Feb 06 '11 at 18:52
  • As per your own comment above, binary search **will** work with repeated values, it simply results in sub-optimal performance. The key insight in my response above (which Chris' also relies upon) is that after rotation, the array consists of two sub-arrays both of which are still sorted. As such, by definition the algorithms still work, albeit with the performance hit you describe. They certainly don't *stop* working. – Mac Feb 06 '11 at 20:07
  • @Mac: They don't work. There are cases where the algorithm will claim the array contains no such element, while it does. My comment to the question does not apply to yours or Chris' algorithm. It talks about _correct_ algorithms. Any correct algorithm will have Omega(n) worst case lower bounds. In fact that is enough to _prove_ that these (yours and Chris') algorithms are incorrect, as they are O(logn) in the worst case. btw, if you use @Moron, I will get notified of your response to my comment (it is a feature of this site). –  Feb 07 '11 at 04:06
  • btw, N is supposed to be unknown... –  Feb 07 '11 at 06:54
  • @Moron, There is still one binary search being done. You don't say why the worst case for these algorithms is O(log n). – Pavan Yalamanchili Feb 07 '11 at 09:35
  • @Pavan: Let me ask you: What is the worst case for binary search? Irrespective of whether the array is sorted or not, you halve your input with each compare, don't you? Isn't that O(logn)? –  Feb 07 '11 at 09:38