2.5 Search in Rotated Sorted Array

Search for a number in rotated sorted array, return its index, assuming not duplicate in input array.

Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Logical Steps

1. Figure out which part the mid is in. If A[mid] > A[start], mid must be in left part of array, other wise it must be in right part of array
2. If mid in left part: we are sure when target is in left part and target is smaller or equal than A[mid], left of mid is increasing and we can move end to mid. Otherwise, target must be in right of mid, we move start to mid
3. If mid in right part: we are sure when target is in right part and target is greater than mid, the right part of mid is increasing and we can move start to mid. Otherwise, target must be in left of mid and we move end to mid

Code template

    public int search(int[] A, int target) {
        if (A==null || A.length == 0)
            return -1;

        // initialization
        int start = 0;
        int end = A.length - 1;

        while(start + 1< end) {
            int mid = (start+end)/2;

            // figure out where mid is (left part or right?)
            if (A[mid] > A[start]) {
                /** when mid is in left part of array
                 * only if target is in 
                 * 1. left part of array
                 * 2. <= mid (when target = A[mid], mid may not be first target value)
                 * we cut all "right of mid" search range by moving end to mid
                 */
                if (target >= A[start] && target <= A[mid]) {
                    end = mid;
                }else{
                    start = mid;
                }
            }else{
                /** when mid is in right part of array
                 * only if target in is
                 * 1. right part of array as well
                 * 2. > mid
                 * we cut all "left of mid" search range by moving start to mid
                 */
                if (target <= A[end] && target > A[mid]) {
                    start = mid;
                }else{
                    end = mid;
                }
            }
        }

        // figure out target is start, or end, or not in array
        if (A[end] == target)
            return end;
        if (A[start] == target)
            return start;

        return -1;
    }

Common Mistakes

1. When mid is in left part, use target < A[mid] as comparison condition. When duplicate exists in input array, it may pickup later number with the same value.

    if (A[mid] > A[start]) {
        /** when mid is in left part of array
         * this is an error example
         * when duplicate exists, end may pick up later dup
         * numbers
         */
        if (target >= A[start] && target < A[mid]) {
            end = mid;
        }else{
            start = mid;
        }