送给大家一句话:
总有一天，你会站在最亮的地方，活成自己曾经渴望的模样—— 苑子文 & 苑子豪《我们都一样 年轻又彷徨》
二分查找入门
1 前言
二分算法是一种非常强大的算法！！！
想象你在一本厚厚的字典里查找一个词。这本字典的词都是按字母顺序排列的。如果你像小学生学习拼音那样一页一页翻，肯定效率很低，因为这样你要查很久。二分查找算法就像是一个聪明的查词策略，它可以帮你快速定位到那个词。
使用二分查找时：
- 你会先打开字典的中间，看这一页的词是不是你要找的，如果不是，你再看这个词是在你要找的词的前面还是后面。
- 如果在前面，那你就把后半部分的查找范围排除掉，只在前半部分继续查找；
- 如果在后面，就排除掉前半部分。然后，你再在剩下的那一半中找到中间，重复之前的步骤。
通过这样一分为二，一步步缩小范围的方式，直到找到那个词，这个过程就是二分查找。
这个方法之所以有效，是因为每次查找你都排除了一半的可能性，大大提高了查找效率。就像在一个有序的环境中找东西，知道了规则，就能迅速定位，节省了大量的时间。
二分查找主要有三种模版：朴素算法，左端点算法，右端点算法。下面我们一起来通过题目认识二分查找算法吧！
2 Leetcode 704. 二分查找
上链接！！！704. 二分查找
2.1 题目描述
这是一一道非常经典的二分查找题目，我们来看样例：
- 输入: nums = [-1,0,3,5,9,12], target = 9
- 输出: 4
- 解释: 9 出现在 nums 中并且下标为 4
很好理解二分查找的寻找过程，下面我们来看代码。
2.2 算法思路
- 首先先定义左右端点
- 判断中间是不是满足条件
- 如果大于那么右端点移到中间的左边
- 反之左端点移到中间的右边
- 直到找到为止
这道题无需考虑很多，使用朴素二分查找即可：
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 算法思路
先来看暴力算法，遍历所有的元素，记录起始和终止位置既可以，但是这样就浪费了数组有序的重要特性！！！
那使用朴素算法呢？ 可以是可以，但是时间复杂度会很大！遇到数组全部是目标值的时候，第一次就能命中对应目标值，但要寻找到起始和中止就要遍历所有的元素，这样就和暴力算法没有区别了！所以不推荐朴素算法
算法优化
我们来看朴素算法的优化版本：左端点二分和右端点二分
这道题实际上可以分成两个问题：
- 查找左端点
- 查找右端点
先看左端点：我们可以把数组分为两部分：小于target 的部分 ，大于等于target 的部分。然后我们分类讨论(x 为 中间值)：
1.x < t 那么 left = mid + 1 更新新区间
2.x >= t 那么 right = mid (不能越过mid,因为mid 有可能是答案所在位置) 更新区间
在来看难点 ： 循环条件 和 求中点的操作
循环条件
到底是left < right 还是 left <= right ???我们来分类讨论一下：
- 如果有结果，那么left 是一直想要跳出这个区域，如果相遇那么此位置就是结果（无需判断），如果判断就会陷入死循环
- 如果全大于 t , 那么只能right 移动，最终相遇时，如果是（left <= right ）就会死循环，我们只需判断该值是否等于 t
- 如果全小于 t , 那么只能left 移动，最终相遇时 ，如果是（left <= right ）就会死循环，我们只需判断该值是否等于 t
求中点的操作
求中点也是有两种：
- left + (right - left ) / 2
- left + (right - left + 1) / 2
如果仅剩两个元素时，使用第二种时，如x >= t 那么right 就不动了！！！陷入了死循环！！！
所以要使用第一种！！！
右端点也是同样的分析思路，不同的是：
- x <= t 那么 left = mid 更新新区间
- x > t 那么 right = mid - 1 (不能越过mid,因为mid 有可能是答案所在位置) 更新区间
- 求中点操作要用第二种办法
这样就完成了：
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; } };
提交：过啦！！！！
