解法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;
}
};