【专题刷题】二分查找（一）：深度解刨二分思想和二分模板

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

二分查找算法介绍

因为我之前用python写题的时候也写过二分查找，也有点心得：
https://blog.csdn.net/tan_run/article/details/145514702
如今再学，任深感不足。通过 704 和 34 题再度感受和理解二分查找。

---

704. 二分查找

暴力解法：
遍历数组，依次和target比较，时间复杂度：O(n)

暴力解法的局限在于：每次只能判断一个数，没有利用数组升序的特点

更好的解法：二分查找。利用数组有序的特点，那怎么利用呢？

假设我们随机取一个下标i，将nums[i]与target比较，如果nums[i] < target，又因为数组有序，所以：nums[i]左边的数都小于target，我们就可以直接排除左边的区间。

而上面所体现的也叫做二段性：每次“选点”，通过该点可以让我们把探索区域划分成两份，并且能够排除一段区域。（只是选中点的时候，数学期望最小（易证），所以我们通常取中点，也叫做二分）

朴素二分查找模板

闭区间写法：

• .......：根据二段性的特点来填写
• while(left <= right)：因为是闭区间写法，区间不为空，还要判断
• left + (right - left) / 2：防溢出写法

---

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

暴力解法：
从头到尾遍历数组，时间复杂度：O(n)

二分查找（利用二段性）：

• 先找左端点：左端点左边的元素 < t；左端点及左端点右边的元素 >= t。于是，我们就可以发现二段性：当nums[mid] < t，左端点一定严格在mid的右边[mid + 1, right]（画图很好理解） ，left更新为mid + 1；当nums[mid] >= t的时候，左端点一定在[left, mid]，mid位置不能排除，因为有可能mid就是左端点，right更新为mid
• 上面这种方法其实是左闭右开区间的写法，right所在位置已经判断过了，循环条件为while(left < right)，因为当 left == right 的时候已经是空区间，循环不变量：right始终指向 >= t 的数字
• 求中点操作：在左闭右开这种写法里面，当有两个中间值时（数组长度为偶数），必须要选择前一个：left + (right - left) / 2

重点：以上总结找左端点>=（左闭右开区间写法）：

• 如果nums[mid] < t，则右端点肯定在：[mid + 1, right]
• 如果nums[mid] >= t，则右端点肯定在：[left, mid]
• 循环条件，while(left < right)（因为是左闭右开的）
• 求中点操作：left + (right - left) / 2 取前面的中点
• 循环不变量：right始终指向第一个>= t的数

PS：多举例子，找极端例子看特殊情况

当然我们也可以直接写找右端点<=的：

• 如果nums[mid] <= t，则右端点肯定在：[mid, right]
• 如果nums[mid] > t，则右端点肯定在：[left, mid - 1]
• 循环条件，while(left < right)（因为是左开右闭）
• 求中点操作：left + (right - left + 1) / 2 取后面的中点

其他方法：在>=的基础上转换：

题解代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0){return {-1, -1};}// 二分左端点 >= int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2; // 防止溢出if(nums[mid] < target)left = mid + 1;elseright = mid;}if(nums[right] != target)return {-1, -1}; // 代表没有targetint begin = right;// 找右端点（左端点不重置）left = begin, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};

二分模板

口诀：

• mid：下面出现 -1，上面就要 +1
• if...else...：根据二段性写出

为什么呢？

首先，左右两种模板的取mid区别是：左边是向下取整，右边是向上取整

以右边模板为例：
右边模板的收缩范围：[mid, right] 或 [left, mid - 1]
如果此时剩余区间为：[right - 1, right]，向下取整则mid = right - 1。如果，最后的判断进入if，则left = mid = right - 1和原来无异，就会死循环。
如果是向上取整：mid = right，进入if：left = right，进入else：right = right - 1，两条语句都变化了，就不会死循环

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！