What is the best way to do a binary search in a sorted array that has been rotated N times

Question

Possible duplicate:
Number search in expanded sorted array

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

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 may have any value and may be greater than the number of elements.

Answer 1

Short answer: you are not (at least not the whole array at once). This is because binary searches require sorting elements to work.

What 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 . 8 15 and 1 4 5 are still sorted, so you can binary search for each of these submatrices. In a general sense, the algorithm becomes as follows:

 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 limit your search to A1 or A2 based on the first element of A is that if A [0]> T, then all elements of A1 will also be> T by definition, and therefore T cannot be in A1.

NTN!

EDIT As Chris points out in subsequent comments, there is a much simpler approach than this, which actually allows you to continue performing a binary search over the entire array. While the above will work, his approach inventively performs a similar function, but throughout the array, using a modified comparison operation.