LeetCode 33. 搜索旋转排序数组
原题链接
中等
作者:
冷丁Hacker
,
2022-02-28 15:58:54
,
所有人可见
,
阅读 144
class Solution {
//这道题目非常适合练习二分
public:
int search(vector<int>& nums, int target) {
int l=0,r=nums.size()-1;
//二分找到分解点,第一个区间是逐渐递增的大于nums[0]的
//找到大于nums[0]的最后一个数,对应最小求最大
//每次更新是l=mid;
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]>=nums[0])l=mid;
else r=mid-1;
}
//找到了分解点后,如果target大于num[0],则他在第一段区间
//如果小于,则他在第二个区间
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;
// }
while(l<r){
int mid=l+r+1>>1;
if(nums[mid]<=target)l=mid;
else r=mid-1;
}
if(nums[r]==target)return r;
return -1;
}
};