解法1：暴力从左到右搜索。

解法2：二分搜索。
思路： 由于至少能保证一边是有序的，所以可以用二分；对不是有序的那一边，同样的道理，至少能保证一般是有序的，不断把规模缩小

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int left = -1, right = nums.size();
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (right == mid + 1) return -1;// 要保证()区间内是有值的，不然可能会越界！！！
            if (nums[0] < nums[mid]) { //左边有序
                if (target >= nums[left + 1] && target <= nums[mid - 1]) { //如果tagert在该区间
                    right = mid;
                }else {
                    left = mid;
                }
            }else { //右边有序
                if (target >= nums[mid + 1] && target <= nums[right - 1]) {
                    left = mid;
                }else {
                    right = mid; 
                }
            }
        }
        return -1;
    }
};