image.png
二分查找的扩展
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
int start = 0;
int end = nums.size() - 1;
while(start + 1 < end){
int mid = start + (end - start) / 2;
if(target == nums[mid]) return mid;
if(nums[start] < nums[mid]){//可判断start 到 mid 是有序的。
if(target >= nums[start] && target <= nums[mid]){
end = mid;
}
else{
start = mid;
}
}
else{ // 可判断mid 到 end 是有序的
if(target >= nums[mid] && target <= nums[end]){
start = mid;
}
else{
end = mid;
}
}
}
if(nums[start] == target) return start;
if(nums[end] == target ) return end;
return -1;
}
};
