Leetcode33: 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.

本题是binary  search 的变种， 一个array可以分成两部分，这两个部分分别都是sorted的，有两种情况： case1: left ->mid是递增的，这表明rotated的array后大半部分被rotated到了前面； case2: mid->right是递增的，这表明rotated 的array后小半部分被rotated到了前面。分别对这两种情况进行bianry search的处理。
特别注意的是：因为mid的值在偶数情况下是靠左侧，所以当判断left -> mid是否是递增的时候，判断条件是num[left] <= num[mid]，这种情况将left 和 mid指向同一个数字的情况考虑进去。 simple case : num: 3,1 target: 1 
class Solution {
public:
    int search(vector<int>& nums, int target) {
        //sanity check
        if (nums.size() == 0) return -1;
        int left = 0;
        int right = nums.size()-1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (target == nums[mid]) return mid;
            if (nums[left] <= nums[mid]) { //left->mid increasing order
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            } else {//mid->right increasing order
                if (target <= nums[right] && target > nums[mid]) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }
        return -1;
    }
};
time complexity: O(logn)