【C/C++算法】从浅到深学习--- 二分查找（图文兼备 + 源码详解）

绪论：冲击蓝桥杯一起加油！！

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”

绪论​：
本章是算法篇章的第三章二分算法，本章主要是通过题目的形式来进行学习，通过八道题让你基本了解二分法算法以及它的许多细节，在简介部分将会一定性的总结二分算法编写时的细节，通过这些了解这些细节，然后再通过前两道题了解二分算法的常见三种模板，再通过6道题巩固相信你对二分算法就会有很大的提升，后面将持续更新前缀和算法，敬请期待~
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。

二分查找算法简介

对于二分查找是什么，它的由来啥的就不过诉了，这是一个算法快速学习文章，我们通过几道题其实就能很好的理解什么事二分算法了！

特点：

1. 最恶心、细节最多
2. 最容易写出死循环算法
3. 掌握后 ----》 最简单

学习的侧重点：

1. 算法原理：数组有序的情况（不准确），应该是：发现数组有二段性规律就能使用二分
2. 模板（不要死记硬背，理解后记忆）
   1. 朴素二分（简单但局限）
   2. 查找左边界的二分模板
   3. 查找有边界的二分模板（后面两个，较为万能，但细节很多）

注意：

1. 从有一定单调性中的数据中，直接通过答案分析二段性（中间值，左端点，右端点）

2. 二段性并不代表：

   1. 它不一定只是左边小右边大的
   2. 它本质是通过分析题目画出图形，查看是否能通过两个公式得出所有情况

总结（如何分析是否使用二分算法）：

1. 分析题目，画出图形
2. 直接根据答案分析图形，看看是否能写出二段性公式
3. 最终确定二段性，然后根据二段性情况分析使用模板一、二、三

具体训练：

1. 二分查找（非常重要的模板二分题）

题目：

分析题目并提出，解决方法：

1. 暴力解法：很简单就是直接遍历一遍数组即可

但还有更加优秀的算法分析题目：

• 对于暴力解法来说，他每次比较仅仅只能排除一个数
• 但题目是有序的，却没用到，这里可以利用起来

1. 现在随便获取一个数4 拿 target 与它进行比较
2. 发现能一次排除多个数（如下图）
   
3. 取出 4 < t（target） ，那么 4 左边区间的都可以直接排除了，因为他是升序的，4 都小于target了，那么其左边的值只会更小！

这个方法，画成如下图方框内：发现其实本质通过一个数将数组划分成 “二段性”

通过一次比较将数组一下子划分成两部分：

二段性的本质并不只是找最中间的值，而是将数组划分成两部分的任意一点（如下图）

但还是得选择使用第一种最中间的点（因为这种在数学上效率是最高的）

模板一

二分模板主要以下步骤：

1. 使用left、right双指针确定区间
2. 每次从区间中获取mid最中间的值（mid = left + (right - left) / 2），然后和target值进行比较
   
3. 只会用下面的三种情况
   1. mid < target
   2. mid > target
   3. mid == target
   4. 当为上面三种情况时，他们的区间如何变化
   5. 很好理解 当 x < t 时：代表 mid及左边的区间都无效，那么left指针移动：left = mid + 1
   6. x > t：则类似意思：right = mid - 1（x 及 x右边区间 都无效）
   7. x == t。那就代表找到了正确区间！
      

细节问题：

1. 循环结束的条件
   1. left > right 才结束循环（循环条件就是 left <= left）
   2. 因为left == right的值可能也需要进行判断，而判断后就会 left > right
   3. 所以不能是 left < right
2. 求中间的值的mid 可以使用 （right - left）/ 2 + 1
3. 时间复杂度
   

题解核心逻辑：

该题就是最基础的二分题，直接使用上述模板即可做出：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0 ,right = nums.size() - 1;
        int mid,res = -1;
        while(left <= right)
        {
            mid = ((right  - left) / 2) + left;//防止溢出
    
            if(nums[mid] < target){
                left = left + 1;
            }else if(nums[mid] > target){
                right = right - 1;
            }else{
                return mid;
            }
        }

        return -1;
    }
};

2. 在排序数组中查找元素的第一个和最后一个位置（非常重要的模板二分题）

题目：

分析题目并提出，解决方法：

非递减：代表要么递增，要么不变

暴力解法：遍历得到begin，end位置

题解核心逻辑：

分析本题要找的是一个值的区间：找左端点、右端点

拿左端点为例先直观的看出答案，然后进行分析，分析出其其实也是有二段性的

那么先使用二分模板一解决：

发现无法解决：虽然也能通过找到target的位置但还需要遍历左右两边，但这种的最大时间复杂度又变成了O(N)了

模板二：查找左端点的情况

光先看左端点来说：分析出它的二段性（如下图）

1. x < t：left = mid + 1（ mid + 1 因为结果一定不会在mid及其左边）
2. x >= t：right = mid（ mid 因为结果可能就是当前的值，我们不能跳过）

但其中有很多细节问题：

1. 循环条件：使用left < right（而不是 left <= right）
   1. 当有结果的时候，若left = right还要进入的话，此时 x >= t 的那么将会执行 right = mid 的操作，这样的话就会导致right值又再一次重复的设置为了 mid，那么就将会死循环，所以说当有结果的时候是不用判断 left == right这个地方的！
      
   2. 当数组中的值全部大于 t，那么right最终将移动到最左端和left相遇，那么其也是一样的不用进去 不然就死循环了
      
   3. 同理 left会不断的移动到最左边，他有两种情况，一种是和right相遇（那么就和上面一样不需要进去），还有就是超过right那么就肯定出循环了 就不用考虑
      
   4. 综合上面3种情况，已经包括了所有的可能，总结出当left = right 的时候是不要进入循环的，那么也就推道出使用 left < right
2. 求中点mid：使用left + （right - left）/ 2（尽量不要死记）
   1. 对于找右端点来说 left每次移动 mid + 1，right 每次移动 mid
   2. 在我们求中点的操作来说是使用下述两个，但假如使用了第二种：left + (right - left + 1)就会死循环
   3. 为什么呢：因为这两个找中间值的操作本质他们的区别是在偶数时，让mid指向左边还是右边（例如 1 2 3 4 第一种方式就会找到的中点为 2，第二种方式找到的中点就会为3，具体自己算哈~）
   4. 那么回来为什么找到右边就不能用呢，是因为假如在极端情况下只剩两个数字了，left指向第一个数字，right指向第二个数组（具体如下图情况）
   5. 而此时要找的是左端点，就需要left < right 出循环，但因为right的移动是等于mid的
   6. 而此时mid求出来的却是右边和right指向的相同，还是 nums[mid] >= t，right = mid
   7. 那么就会导致right还是没有移动，再次进入循环，算mid还是一样的，right的移动还是前面的，这样就会导致死循环
   8. 这样说可能还是有点抽象，为了方便记忆：可以把 求中点方程式里面的 +1 想象成mid的位置（+1就是在右边，不+1就是在左边，通过下图右边记住mid的位置），本题是 right 移动 mid步（找左端点…），那么mid在右边的话就会和right重叠，所以不能+1；
      

模板三：查找右端点：

和上面就几乎一致了，只不过二段性不一样，并且找中点不一样

对于找中点来说：因为此处的是left = mid，那么若是用 left + (right - left) / 2的话，就剩两个值时求mid就会移动到左边，和left重叠导致，死循环（和上面左边分析一致就不过诉了，若不懂可以评论细讲哈~）

最终做题，找到左右端点：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0 , right = nums.size()-1;
        int mid;
        vector<int> res;
        if(nums.size() == 0) return {-1,-1};
        //找左端点
        //不要进入，不让 right可能会无限的等于mid
        while(left < right){
            mid = left + (right - left) / 2;//内部不要+1 因为在只有两个值的时会导致 right不断的等于mid 而用于到达不了最左端
            if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        //出循环判断有结果的情况：
        //两种移动情况出循环：
        // left = mid + 1: left >= right 其中left 不可能大于 right（只能left == right 循环）
        // 因为要打的前提是 left == right（因为只有 right(left) + 1 > right）
        // 
        // right = mid 而就肯定是left == right了也不可能越界
        //所以综上所述 left == right
        if(nums[left] == target){
            res.push_back(left);
        }else{
            //若不等则表示没找到
            return {-1,-1};
        }
        //重置left right
        left = 0;right = nums.size()-1;
        //查找右端点：
        //left < right，相等可能会导致死循环 left 不断的等于 mid
        while(left < right){
            mid = left + (right - left + 1) / 2;// +1 让mid移动到右边，防止和left重叠！！！
            if(nums[mid] <= target){
                left = mid;//等于mid是因为防止错过正确的target
            }
            else{
                //nums[mid] > target
                right = mid - 1;//right 往右移动 -1
            }
        }
        //出来肯定是left == right，所以随便用，前面使用left这里使用right
        if(nums[right] == target){
            res.push_back(right);
        }else{
            //若不等则表示没找到
            return {-1,-1};
        }
        return res;
    }
};

3. x 的平方根

题目：

分析题目并提出，解决方法：

分析暴力解法：从1并计算出平方，会有两种情况：

1. 平方 小于 目标值，继续找
2. 平方 等于 目标值，那么就找到了
3. 平方 大于 目标值，那么表示超过了，那么就取该值前面的那个数
   

优化，分析上图：

1. 首先他是有序的
2. 并且发现是有二段性的：
   
   而此处分析题目可知：
   答案可能是：在小于区间的和刚好找到的，所以也就是找左端点的移动情况（具体如下图）
   

题解核心逻辑：

class Solution {
public:
    int mySqrt(int x) {
        if(x < 0) return 0;
        //找左端点
        long long left = 0,right = x;
        
        int i  = 0;
        //使用mid中点的平方来进行快速的查找
        while(left < right) {
            long long mid = left + (right - left + 1) / 2;//因为是left 所以mid要 +1，防止重叠
            if((long long)mid * mid <= x){
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
};

4. 搜索插入位置

题目：

分析题目并提出，解决方法：

本题是一个非常明显的二分：有序 + 查找值（只不过是查找目标位置）
分析本题：需要找到是插入的位置，分析示例：

直接看出插入的位置，分析他插入的位置：是大于等于的区间，所以也就是找右端点

题解核心逻辑：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0,right = nums.size() -1;
        while(left < right){
            int mid = left + (right - left) / 2;//这里是找right，所以不+1
            if(nums[mid] < target){
                left = mid + 1;
            }
            else right = mid;
        }
        if(nums[left] < target)return left + 1;//处理示例三，但需要放到最后时

        return left;
    }
};

5. 山脉数组的峰顶索引

题目：

分析题目并提出，解决方法：

分析题目：不难想出暴力解法，遍历数组找到第一个 arr[i] > arr[i+1]的值即可

但分析下其中本质也是有二段性的：在峰顶左边：arr[i] >= arr[i-1]，峰顶右边：arr[i] < arr[i-1]（具体如下图）

题解核心逻辑：

通过上面的分析出了二段性：
其中再次强调二段性本质是通过某个式子将数组分组两块，而这个式子就是left、right的移动方法，其中包含答案的区域移动就是mid步！
而本题答案是在左端点的所以left = mid（这题右端点也能使用，不过左端点更符合思考逻辑）

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0,right = arr.size()-1;
        if(arr.size() == 1) return 0;
        while(left < right){
            int mid = left + (right - left + 1) / 2;
            if(arr[mid] >= arr[mid-1]){
                left = mid;
            }else{
                //arr[mid] < mid - 1
                right = mid - 1;
            }
        }
        return left;
    }
};

//右端点解法：
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 0,right = arr.size()-1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(arr[mid] >= arr[mid+1]){
                right = mid;
            }else{
                //arr[mid] < mid - 1
                left = mid + 1;
            }   
        }
        return left;
    }
};

6. 寻找峰值

题目：

分析题目并提出，解决方法：

分析题目：不难想出其暴力解法的三种情况：

分析题目：
其实也对于某个点 i 来说，它的左右相邻的数无非两种情况:

1. arr[i] > arr[i + 1]：此时峰值在 i 的左区间一定会出现，所以再次查找左区间就够了，如果要找左区间对于 right= mid(i) 即可（mid已经指向了左区间）
2. arr[i] < arr[i+1]：此时峰值在 i 的右区间一定会出现，所以查找右区间就够了，查找右区间：因为 i 位置肯定不是所以 left = mid + 1
3. 最终当left 和 right 相遇则找到了结果
   
   将上图二段性再分析下得二分中指针移动情况：
   
   本题也能很好的说明：二分查找并不一定只是在有序的地方使用的，本题就是一个无序的数列
   本题和上一题本质非常像，只不过分析不一样，但我们一定要注意分析的过程，通过简单的例子直接看出答案进行分析，得出二段性（能区间划分成两块的式子）

题解核心逻辑：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0,right = nums.size()-1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[mid + 1]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
};

7. 寻找旋转排序数组中的最小值

题目：

分析题目并提出，解决方法：

其中暴力解法很简单：简单遍历计数器记录得出结果（但本题要去logn的时间复杂度那么很明显可能就是二分）

分析题目画出如下折线图（明显的二段性）：

既然是二段性不妨好好的看一下图形，分析出其中的如何通过式子得出二段性
分析可知其中可以使用D点，进行和mid的值进行比较，就会只有两种可能（具体如下图）

1. 当mid指向A ~ B区间的时候， mid的值一定大于D点的值
2. 当mid指向C~D区间的时候，mid值是小于等于D点的值的

题解核心逻辑：

最终通过二段性也得出二分的公式：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        int d = nums[right];
        while(left < right){
            int mid  = left + (right - left) / 2;//不用 + 1 right = mid
            if(nums[mid] > d){
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }
        return nums[right];
    }
};

此处不直接拿A点是因为假如它没有选择那么就是一个递增的，就会出现一定的问题！

但也能做出来只需要将这种情况给排除即可：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        int a = nums[0];
        if(a < nums[right]){//判断第一个点和最后一个点，若小则代表没有旋转过
            return a;
        }
        while(left < right){
            int mid  = left + (right - left) / 2;//不用 + 1 right = mid
            if(nums[mid] >= a){//在A~B区间
                left = mid + 1;
            }
            else{
                right = mid;
            }
        }

        return nums[right];
    }
};

8. 点名特别奇怪的二段性！

题目：

分析题目并提出，解决方法：

分析题目不难想出下面4种解法：

题解核心逻辑：

而本题仍然可以二段性：
这个二段性比较奇怪，我们借助数组小标来查看它的二段性，发现：

1. 前半段下标和数字一致
2. 后半段下标比数字小1（具体如下图）
   
   那么就推出二分公式：
   

其中注意一个边界情况：

当缺失的是最后的值，那么需要出循环后，因为他是不断的向右移动的，最终会到达最后然后出循环，此时判断最后一个值它的下标是否符合，若相等则表示缺少是最后的值（也就是上图的4），反之若不相等则表示正常出循环

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0,right = records.size()-1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(records[mid] == mid){
                left = mid + 1;//在左区间
            }
            else right = mid;
        }
        //如果right 到达最后 再次判断是否和下标相等，若相等则表示是 最后值的 下一个 缺少了
        if(records[right] == right) return right + 1;
        return right;
    }
};