題目描述

可以發現的是，將數組從中間分開成左右兩部分的時候，一定至少有一部分的數組是有序的。左部分[left,mid-1]，右部分[mid+1,right]。

第一種情況：左右兩部分都是有序的，說明nums[mid]就是整個數組的最大值。此時只需要判斷target在哪個部分，然后去那個部分做正常的二分查找即可。

第二種情況，左右兩部分只有一部分是有序的。此時看target是否在有序的那部分。如果是，那就去有序的那部分做正常的二分查找。如果否，說明target在無序的部分，并且問題規模縮小一半，重復前面的邏輯即可。

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() -1;int mid = 0;while(left<=right){mid = left + ((right-left)>>1);if(nums[mid] == target)return mid;if(left <= mid-1 && nums[left] <= nums[mid-1])//左半部分有序{if(nums[left]<=target&&target<=nums[mid-1])//target在左半部分之中right = mid-1;elseleft = mid +1;}else//右半部分有序{if(mid+1<=right && nums[mid+1]<=target&&target<=nums[right])//target在右邊部分之中left = mid+1;elseright = mid -1;}}return -1; }
};