Search in a rotated sorted array

Given a sorted array which has been rotated such as A = {5,6,1,2,3,4}, find an element in it.

If the array is sorted, we can perform a binary search on the array. We partition the array into two halves, say left and right. We determine the half in which the element can be found and proceed by reducing the problem by half at each step. The complexity is O(log n).

If the array is rotated after sorting, we partition the array into two halves, say left and right. In this case, only one half is sorted. We determine if the search element can be found in the sorted half or the unsorted half. If the element is in the sorted half, we perform a binary search on that half. If the element is in the unsorted half, we proceed by recursively applying our algorithm to the unsorted half. We continue the process until we have found the search element or we have no more elements in the partition (in which case, the search element is not found). At each step, we are reducing the problem by half. The complexity of this approach is O(log n).

Here is the C++ code:

void FindInRotatedArray(const int* a, int key, int low, int high) {

  while(low <= high) {

  int mid = (low + high) / 2;

  if(key == a[mid]) { //found the key

    cout << "Found the key at " << mid << endl;

    return;

  }

// the left half is sorted

  if (a[low] <= a[mid]) {

    if (a[low] <= key && key < a[mid]) //key is in the sorted half

      high = mid - 1;

    else

      low = mid + 1; //key is in the unsorted half

  }

// the right half is sorted

  else {

    if (a[mid] < key && key <= a[high]) //key is in the sorted half

      low = mid + 1;

    else

      high = mid - 1; //key is in the unsorted half

  }

}

cout << "Key not found" << endl;

}

Invoke the function as: FindInRotatedArray(a,6,0,5);