33 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.

Solution

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if ( n == 0 ) return -1;
        int l = 0, r = n-1, mid;
        if ( nums[0] == target ) return 0;
        if ( nums[n-1] == target ) return (n-1);
        while ( l <= r-2 ) {
            mid = (l+r)/2;
            if ( nums[mid] == target ) return mid;
            if ( nums[l] < nums[mid] ) { 
                if ( target < nums[mid] and target > nums[l]) {r = mid; continue;}
                else { l = mid; continue;}
            }
            if ( target > nums[mid] and target < nums[r] ) { l = mid; continue;}
            else { r = mid; continue;}
        }
        return -1;
    }
};

Notes
Consider the following rotated sorted array:

[4,5,6,7,0,1,2]

• For any (i, j) pair, if nums[i] < nums[j], then the sub-array nums[i:j+1] is monotonous increasing.
• For any binary partition, there always exists one monotonous interval.
• We only have to examine whether target is in this monotonous interval!

Follow up
What if duplicates are allowed?

[4,5,6,7,0,1,2,4,4]

What is the difference?

Example, 
Given nums = [1,1,3,1], target = 3

One has to "get rid of" the duplicates at the two heads of the array.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if ( n == 0 ) return false;
        int l = 0, r = n-1, mid;
        if ( n == 1 ) return (nums[0] == target);
        while ( l <= n-2 and (nums[l] == nums[l+1] or nums[l] == nums[r] )) l += 1;
        while ( r >= 1 and ( nums[r] == nums[r-1]) ) r -= 1;
        if ( nums[l] == target ) return true;
        if ( nums[n-1] == target ) return true;
        while ( l <= r-2 ) {
            mid = (l+r)/2;
            if ( nums[mid] == target ) return true;
            if ( nums[l] < nums[mid] ) { 
                if ( target < nums[mid] and target > nums[l]) {r = mid; continue;}
                else { l = mid; continue;}
            }
            if ( target > nums[mid] and target < nums[r] ) { l = mid; continue;}
            else { r = mid; continue;}
        }
        return false;
    }
};