如何用二分法搜索、查找旋转数组中是否含有某个（目标）值？ leetcode 81.搜索旋转排序数组

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…
欢迎参与CSDN学习挑战赛，成为更好的自己，请参考活动中各位优质专栏博主的免费高质量专栏资源（这部分优质资源是活动限时免费开放喔~），按照自身的学习领域和学习进度学习并记录自己的学习过程。您可以从以下3个方面任选其一着手（不强制），或者按照自己的理解发布专栏学习作品，参考如下：

一.题目描述

---

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。
示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

二.代码

---

class Solution {
    
public:
    bool search(vector<int> &nums, int target) {
    
        int start = 0, end = nums.size() - 1, mid = 0;
        while(start <= end) {
    
            mid = (start + end)/2;
            if(nums[mid] == target) {
    
                return 1;	//true
            }
            
            //不能判断哪一半是有序的
            if(nums[mid] == nums[start]) {
    
                ++start;
            }else if(nums[mid] > nums[start]) {
    
            //mid左侧有序，判断target是否存在于该有序的序列中。
                if(target >= nums[start] && target <= nums[mid]) {
    
                    end = mid - 1;
                }else{
    
                    start = mid + 1;
                }
            }else{
    
            //右侧有序
                if(nums[mid] <= target && target <= nums[end]) {
    
                    start = mid + 1;
                }else{
    
                    end = mid - 1;
                }
            }
        }
        return 0;
    }
};

三.思路

---

1.大致方向

二分法的使用条件是递增或递减序列，而旋转数组并不是严格的递增或者递减序列，所以我们要：
1.通过二分把旋转数组分成有序的一半和无序的一半，（例如： 对于数组 [2,3,3,3,4,4,4,5,6,7,1] 来说，第一次二分后 有序的一半是[2,3,3,3,4],无序的一半是[4,5,6,7,1]）；
2.如果要找的值存在于有序的一半，那么使用常规的二分流程就可以了；
3.如果要找的值存在于无序的一半，那么重复该流程（把当前数组[4,5,6,7,1]二分为[4,5]和[7,1]两部分）。

2.细节

变量及意义：
start 二分的数组左侧下标，初值是0；
end 二分的数组右侧下标，初值是nums.size();
mid 二分的数组中间下标，值为 (start + end)/2;
@如何判断哪一半是有序的呢？
@如果二分时的 nums[mid] > nums[start],那么mid左侧是有序的。
@如果二分时的 nums[mid] < nums[start],那么mid右侧是有序的。
@如果二分时的nums[mid] == nums[start] ，不能确定哪一半是有序的，此时令 start = start + 1,效果 是mid向右移动了一位。