Search an element in rotated sorted array

arr.cpp

/*
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;
}