送给大家一句话:

总有一天，你会站在最亮的地方，活成自己曾经渴望的模样—— 苑子文 & 苑子豪《我们都一样 年轻又彷徨》

1 前言

二分算法是一种非常强大的算法！！！
想象你在一本厚厚的字典里查找一个词。这本字典的词都是按字母顺序排列的。如果你像小学生学习拼音那样一页一页翻，肯定效率很低，因为这样你要查很久。二分查找算法就像是一个聪明的查词策略，它可以帮你快速定位到那个词。

使用二分查找时：

1. 你会先打开字典的中间，看这一页的词是不是你要找的，如果不是，你再看这个词是在你要找的词的前面还是后面。
2. 如果在前面，那你就把后半部分的查找范围排除掉，只在前半部分继续查找；
3. 如果在后面，就排除掉前半部分。然后，你再在剩下的那一半中找到中间，重复之前的步骤。

通过这样一分为二，一步步缩小范围的方式，直到找到那个词，这个过程就是二分查找。
这个方法之所以有效，是因为每次查找你都排除了一半的可能性，大大提高了查找效率。就像在一个有序的环境中找东西，知道了规则，就能迅速定位，节省了大量的时间。

二分查找主要有三种模版：朴素算法，左端点算法，右端点算法。下面我们一起来通过题目认识二分查找算法吧！

2 Leetcode 704. 二分查找

上链接！！！704. 二分查找

2.1 题目描述

这是一一道非常经典的二分查找题目，我们来看样例：

• 输入: nums = [-1,0,3,5,9,12], target = 9
• 输出: 4
• 解释: 9 出现在 nums 中并且下标为 4

很好理解二分查找的寻找过程，下面我们来看代码。

2.2 算法思路

1. 首先先定义左右端点
2. 判断中间是不是满足条件
3. 如果大于那么右端点移到中间的左边
4. 反之左端点移到中间的右边
5. 直到找到为止

这道题无需考虑很多，使用朴素二分查找即可：

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

下面的题目我们来详细讲解左端点二分和右端点二分！

3 Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置

上链接！！！34. 在排序数组中查找元素的第一个和最后一个位置

3.1 题目描述

这道题分别要寻找目标值的开始索引和终止索引。来看样例：

• 输入：nums = [5,7,7,8,8,10], target = 8
• 输出：[3,4]

3.2 算法思路

先来看暴力算法，遍历所有的元素，记录起始和终止位置既可以，但是这样就浪费了数组有序的重要特性！！！
那使用朴素算法呢？ 可以是可以，但是时间复杂度会很大！遇到数组全部是目标值的时候，第一次就能命中对应目标值，但要寻找到起始和中止就要遍历所有的元素，这样就和暴力算法没有区别了！所以不推荐朴素算法

算法优化

我们来看朴素算法的优化版本：左端点二分和右端点二分
这道题实际上可以分成两个问题：

1. 查找左端点
2. 查找右端点

先看左端点：我们可以把数组分为两部分：小于target 的部分 ，大于等于target 的部分。然后我们分类讨论(x 为 中间值)：

1. x < t 那么 left = mid + 1 更新新区间
2. x >= t 那么 right = mid (不能越过mid,因为mid 有可能是答案所在位置) 更新区间

在来看难点 ： 循环条件 和 求中点的操作

循环条件

到底是left < right 还是 left <= right ???我们来分类讨论一下：

1. 如果有结果，那么left 是一直想要跳出这个区域，如果相遇那么此位置就是结果（无需判断），如果判断就会陷入死循环
2. 如果全大于 t , 那么只能right 移动，最终相遇时，如果是（left <= right ）就会死循环，我们只需判断该值是否等于 t
3. 如果全小于 t , 那么只能left 移动，最终相遇时 ，如果是（left <= right ）就会死循环，我们只需判断该值是否等于 t

求中点的操作

求中点也是有两种：

1. left + (right - left ) / 2
2. left + (right - left + 1) / 2

如果仅剩两个元素时，使用第二种时，如x >= t 那么right 就不动了！！！陷入了死循环！！！
所以要使用第一种！！！

右端点也是同样的分析思路，不同的是：

1. x <= t 那么 left = mid 更新新区间
2. x > t 那么 right = mid - 1 (不能越过mid,因为mid 有可能是答案所在位置) 更新区间
3. 求中点操作要用第二种办法
   这样就完成了：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1,-1};
        int begin = 0 , end = 0;
        int left = 0, right = nums.size() - 1;
        //先找左点
        //左边都小于 t 右边大于等于 t 
        //左边不合法 右边合法
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] == target) begin = left;
        else return {-1,-1};
        //进行右边操作
        //左边都小于等于 t 右边大于 t 
        //左边合法 右边不合法
        left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        end = right;
        return {begin,end};
    }
};

提交就过啦！！！

Leetcode 35. 搜索插入位置

家人们！！！上链接！！！35. 搜索插入位置

题目描述

这道题很好理解，找到对应位置插入即可！！！

算法思路

当然暴力算法很好想，但是我们不用。
通过上一道题的思路，我们很容易想到使用左端点二分的方法，因为插入是在该数的前面插入。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0 , right = nums.size() - 1;
        int ans = 0;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //避免比最大的数大，此时是在后面插入
        if(left == nums.size() - 1 && target > nums[left]) ans = left + 1;
        else ans = left;
        return  ans ; 
    }
};

提交！过啦！！！！

Leetcode 69. x 的平方根

上链接！！！69. x 的平方根

题目描述

这道题很好理解奥，我们要实现找到算术平方根。即平方小于x 的最大的数。

算法思路

暴力算法很好想，一个一个试就可以，但是使用二分算法更加快速。
我们可以把数字抽象为左右端，left 为 0 right = x 。然后开始二分（判断条件是mid 的平方与x的比较）。因为是找最大的所以使用右端点二分。

class Solution {
public:
    int mySqrt(int x) {
    	//初始化 右值设置为 x 的一半进一步可以避免平方超范围
        int left = 0 , right = x / 2 + 1;
        while(left < right)
        {   // 使用long long =防止超出int范围
            long long  mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid ;
            else right = mid - 1 ;
        }
        return left;
    }
};

提交：过啦！！！！

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！