思路：每次取中间元素，一定有一半有序，另一半部分有序，有序的部分进行二分查找，部分有序的部分递归继续处理。
class Solution {
public:
int pos = -;
int middleSearch(int left, int right,vector<int>& nums, int target){//二分查找
if(left > right || right > nums.size() - || left < )return -;
if(nums[left] == target)return left;
int mid = (left + right) / ;
if(nums[mid] == target)return mid;
if(target>nums[mid]) return middleSearch(mid+,right,nums,target);
else
return middleSearch(left,mid - ,nums,target);
}
void mixSearch(int left, int right, vector<int>& nums, int target){//混合处理
if(left > right || right > nums.size() - || left < ) return;
if(nums[left] == target) {
pos = left;
return;
}
int ans;
int middle = (left + right) / ;
if(nums[middle] > nums[right]) {
ans = middleSearch(left,middle,nums,target);
if(ans == -) mixSearch(middle+,right,nums,target);
else{
pos = ans;
return;
}
}
else{
ans = middleSearch(middle,right,nums,target);
if(ans == -) mixSearch(left,middle - ,nums,target);
else{
pos = ans;
return;
}
}
}
int search(vector<int>& nums, int target) {
mixSearch(,nums.size() - ,nums,target);
return pos;
}
};写的冗余了点，附上简洁的代码：
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = , r = nums.size() - ;
while(l <= r){
int mid = l + (r - l) / ;
if(nums[mid] == target) return mid;
if(nums[mid] > nums[r]){
if(target > nums[mid] || target <= nums[r]) l = mid + ; // condition for pick right side
else r = mid - ; // else, pick left side
}else{
if(target <= nums[r] && target > nums[mid]) l = mid + ; // condition for pick right side
else r = mid - ; // else, pick left side
}
}
return -;
}
};