How to use binary search and find whether the rotation in the array contains a (target) value?Rotate the sorted array leetcode 81. Search

​
​

活动地址：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
            }
            
            //Can't tell which half is in order
            if(nums[mid] == nums[start]) {
    
                ++start;
            }else if(nums[mid] > nums[start]) {
    
            //mid左侧有序,判断targetexists in the ordered sequence.
                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.大致方向

The dichotomy is used with increasing or decreasing sequences,Rotating arrays are not strictly incrementing or decrementing sequences,所以我们要：
1.Divide the rotated array into an ordered half and an unordered half by bisection,（例如： 对于数组 [2,3,3,3,4,4,4,5,6,7,1] 来说,第一次二分后 The ordered half is[2,3,3,3,4],The disordered half is[4,5,6,7,1]）;
2.If the value you are looking for exists in the ordered half,Then you can use the regular binary process;
3.If the value you are looking for exists in the unordered half,Then repeat the process（put the current array[4,5,6,7,1]二分为[4,5]和[7,1]两部分）.

2.细节

variables and their meanings：
start Left subscript of a bipartite array,初值是0;
end The right-hand subscript of the bipartite array,初值是nums.size();
mid The middle subscript of the bipartite array,值为 (start + end)/2;
@How to tell which half is in order？
@If two minutes nums[mid] > nums[start],那么mid左侧是有序的.
@If two minutes nums[mid] < nums[start],那么mid右侧是有序的.
@If two minutesnums[mid] == nums[start] ,Not sure which half is in order,此时令 start = start + 1,效果 是mid向右移动了一位.