当前位置 博文首页 > 林深不见鹿 的博客：精选力扣500题 第15题 LeetCode 33. 搜索旋
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7]在下标3 处经旋转后可能变为[4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums和一个整数 target ，如果nums中存在这个目标值target ，则返回它的下标，否则返回 -1。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4nums 中的每个值都 独一无二nums在预先未知的某个下标上进行了旋转-10^4 <= target <= 10^4(二分) O ( l o g n ) O(logn) O(logn)
1、先找到旋转点，在旋转点左边的点都比nums[0]大，右边的点都比nums[0]小，因此可以用二分找到该点
当nums[mid] >= nums[0]时，往右边区域找，l = mid。
当nums[mid] < nums[0]时，往左边区域找，r = mid - 1。
2、找到旋转点l后，可以知道[0,l - 1],[l,n - 1]是两个有序数组，判断出target的值在哪个有序数组中，确定好二分的区间[l,r]
3、在[l,r]区间中，由于该区域也具有单调性，通过二分找到该值的位置
当nums[mid] >= target时，往左边区域找，r = mid。
当nums[mid] < target时， 往右边区域找, l = mid + 1。
4、若最后找到的元素nums[r] != target，则表示不存在该数，返回-1，否则返回该数值
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty()) return -1;
//先二分转折点 二分>=nums[0]的最右边
int l = 0, r = nums.size() - 1;
while( l < r)
{
int mid = (l + r + 1)/2;
if(nums[mid] >= nums[0]) l = mid;
else r = mid - 1;
}
if(target >= nums[0]) l = 0; //target在左半边区域
else l = r + 1, r = nums.size() - 1; //target在右半边区域
while( l < r)
{
int mid = ( l + r)/2;
if( nums[mid] >= target) r = mid;
else l = mid + 1;
}
if(nums[r] == target) return r;//二分的while循环的结束条件是l>=r，所以在循环结束时l有可能会大于r，此时就可能导致越界，基本上二分问题优先取r都不会翻车。
return -1;
}
};
原题链接：33. 搜索旋转排序数组
