经典二分法查找的进阶题目——LeetCode33 搜索旋转排序数组

题目内容

整数数组 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 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^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

没想到效果可以这么好。

这个题目的话，既然有明确的一个时间复杂度的要求logn，那么我们肯定就不要想遍历的事情了，既然这样，二分自然就是我们第一个要考量的问题，毕竟这个数组本身也是一个单调数组改的，所以二分肯定是有道理的。
既然如此，我们就先思考一下，单调增序列被这样操作过一次之后，有几种可能，实际上应该只有下图这两种：

也就是对应mid位置和两个端口的大小关系。
我们发现，这样分还是有一种情况没有提到，那就是依旧单调，而这种情况就是我们二分操作中的结束情况。直接二分查找即可。

而对于之前的两种情况呢？也好办，我们有一半是单调的，所以判断是否可以在这里进行二分。不能的话，我们就去掉这一半，对于另一半重复这类操作。每次都是一半单调，一半有上有下，再去分。

不过这个地方有一个需要注意的点，就是在数组很小的时候，可能左右mid重合，所以，为了有效的进行判断，我们的判定条件记得要加上等号。（我之前看提示说，所有元素都不一样，就没有care等号，然后被正义制裁了）

代码

class Solution {
    
public:
    int erfen(vector<int>& nums, int target,int l,int r)
    {
    
        int low=l;
        int high=r;
        while(low<=high){
    
            int mid=(low+high)/2;
            if(nums[mid]>target){
    
                high=mid-1;
            }
            if(nums[mid]<target){
    
                low=mid+1;
            }
            if(nums[mid]==target){
    
                return mid;
            }
        }
        return -1;
    }

    int search(vector<int>& nums, int target) {
    
        int l=nums.size();
        int low=0;
        int high=l-1;
        while(low<=high){
    
            // cout<<low<<" "<<high<<endl;
            int mid=(low+high)/2;
            if(nums[mid]>=nums[low]&&nums[mid]<=nums[high]){
    
                if(nums[low]>target||nums[high]<target){
    
                    return -1;
                }else{
    
                    return erfen(nums,target,low,high);
                }
            }
            else{
    
                if(nums[mid]>=nums[low]&&nums[mid]>=nums[high]){
    
                    if(target<=nums[mid]&&target>=nums[low]){
    
                        return erfen(nums,target,low,mid);
                    }
                    else{
    
                        low=mid+1;
                    }
                }
                if(nums[mid]<=nums[low]&&nums[mid]<=nums[high]){
    
                    if(target>=nums[mid]&&target<=nums[high]){
    
                        return erfen(nums,target,mid,high);
                    }
                    else{
    
                        high=mid-1;
                    }
                }
            }
        }
        return -1;
    }
};