33_Search_in_rotated_sorted_array

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = (int)nums.size() - 1, mid;
        while (left <= right){
            mid = (right - left) / 2 + left;
            if (nums[mid] == target){
                return mid;
            }else if (nums[left] < nums[right]){
                if (nums[mid] < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{
                if (nums[mid] < nums[right]){
                    //right hand side is correct, left hand side is wrong
                    if (nums[mid] < target && target <= nums[right]){
                        left = mid + 1;
                    }else{
                        right = mid - 1;
                    }
                }else{
                    //left hand side is correct
                    if (nums[mid] > target && target >= nums[left]){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
            }
        }
        return -1;
    }
};