Created
March 30, 2015 05:27
-
-
Save rohith2506/cd58c3c57c363c864db7 to your computer and use it in GitHub Desktop.
Search an element in rotated sorted array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Here, the simple logic is | |
first check a[low] <= a[mid] if it is, then we are in lower sorted half else upper sorted half. | |
then, check whether the key is in between low & mid, if it is, update right to mid-1, else update left to mid+1 | |
*/ | |
int rotated_binary_search(int A[], int N, int key) { | |
int L = 0; | |
int R = N - 1; | |
while (L <= R) { | |
// Avoid overflow, same as M=(L+R)/2 | |
int M = L + ((R - L) / 2); | |
if (A[M] == key) return M; | |
// the bottom half is sorted | |
if (A[L] <= A[M]) { | |
if (A[L] <= key && key < A[M]) | |
R = M - 1; | |
else | |
L = M + 1; | |
} | |
// the upper half is sorted | |
else { | |
if (A[M] < key && key <= A[R]) | |
L = M + 1; | |
else | |
R = M - 1; | |
} | |
} | |
return -1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment