Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

[Analysis]

At first I thought of using binary search to find the reset index (the 0 in the above example) first, and then use a binary search on the appropriate section. Here is the code of this implementation. The complexity is still O(logN) as this is basically two binary search. The bSearchIndex function returns the reset index, 0 if not rotated and it should never return -1.

class Solution {
    int bSearchIndex(int A[], int n){
        int start = 0;
        int end = n-1;

        while (start <= end) {
            int mid = start + (end-start)/2;
            if (A[mid] > A[end]) {
                start = mid+1;
            } else if (A[mid] < A[end]) {
                end = mid;
            } else {
                return mid;
            }
        }

        return -1;
    }

    int bSearchTarget(int A[], int n, int resetPoint, int target) {
        int start = (target >= A[resetPoint] && target <= A[n-1]) ? resetPoint : 0;
        int end = start == 0 ? resetPoint-1 : n-1;

        if (resetPoint == 0){
            start = 0;
            end = n-1;
        }

        while (start <= end) {
            int mid = start + (end - start)/2;
            if (A[mid] > target)
                end = mid-1;
            else if (A[mid] < target) {
                start = mid+1;
            } else {
                return mid;
            }
        }
        return -1;
    }

public:

    int search(int A[], int n, int target) {
        vector nums;

        int resetIndex = bSearchIndex(A, n);
        return bSearchTarget(A, n, resetIndex, target);
    }
};

However, we don’t necessarily need to know the reset point as pointed out here since we can always deduce on which side resides the target based on the comparison of A[mid] and A[start]. The code is reproduced below.

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

The (A[L] <= A[M]) gives us enough information to know which half of the array is sorted, and if left side is sorted, we can compare key with the upper and lower bound of left side to check if target falls in left side, otherwise, it must fall in right half or doesn’t exist. The function return -1 if L>R.

This is also log(N) since it’s a modified version of binary search. It’s not asymptotically faster but absolutely much easier to write. Though my original version gave me quite a good exercise on writing binary search. 😛

• Algorithm
• binary_search