Search in Rotated Sorted Array

解析：这道题很明显就是二分查找，但和二分查找有所不同，因为序列中的元素只是部分有序的，难点在于如何定位到部分有序的序列
观察可知：由于序列的元素是不重复的，故若当前位置的元素小于或者等于右边缘的元素，那么，从该位置到右边缘元素的序列就是有序序列；反之，则左边缘的元素到该位置的元素的序列是有序序列
1.若nums[mid] < nums[right]，那么mid-right这段序列就是有序序列，只需判断target是否在这个范围之内，如果位于，则按照二分查找进行查找就行；若不在，则target就位于left-mid范围
2.反之， left-mid这段序列就是有序序列，只需判断target是否在这个范围之内，如果位于，则按照二分查找进行查找就行；若不在，则target就位于mid-right范围

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

[1]https://blog.csdn.net/linhuanmars/article/details/20525681