What is the best way to do a binary search on a sorted array which has been rotated N times [duplicate]

This question already has answers here: Closed 12 years ago.

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 n开发者_StackOverflowumber of elements.

---

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.