LeetCode 33. 搜索旋转排序数组
原题链接
中等
作者:
ShineShaye
,
2022-07-06 16:42:59
,
所有人可见
,
阅读 129
1,二分找到旋转点
2,根据target的大小选取区间,二分找target
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if(target >= nums[0])
l = 0;
else
l = r + 1, r = nums.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[r] == target) return r; //返回l会越界
return -1;
}
};