LeetCode 33. 搜索旋转排序数组
原题链接
中等
作者:
lvjc2010
,
2019-07-23 00:27:55
,
所有人可见
,
阅读 1030
class Solution {
public:
int search(vector<int>& nums, int target) {
//先找到最小值,再在其中一半单调区间上寻找
if (nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
int t = nums.back();
while(l<r){
int mid = l+r>>1;
if(nums[mid]>t) l = mid+1;
else r = mid;
}
//判断
if (target>t){
//注意这里是r-1而不是r
return b_search(nums, 0, r-1, target);
}
else{
return b_search(nums, l, nums.size()-1, target);
}
}
int b_search(vector<int>& nums, int l, int r, int target){
if (nums.empty()) return -1;
while(l<r){
int mid = l+r>>1;
if(nums[mid]>=target) r = mid;
else l = mid+1;
}
if (nums[l]==target)
return l;
else
return -1;
}
};