.
.
文章目录
- 前言
- 二分查找
- 搜索插入的位置
- 思路
- x的平方根
- 思路
- 山脉数组的峰顶索引
- 思路
- 寻找旋转排序数组中的最小值
- 思路
- 总结
前言
本专栏上篇博客已经把滑动指针收尾啦
现在还是想到核心——一段连续的区间，有时候加上哈希表用起来很爽
今天我们来学习新的算法知识——二分查找，相信大家都不陌生
二分查找，怎么说呢，清晰了解之后，其实代码就几行
话不多说，跟我一起来瞅瞅吧
二分查找
首先我们来学习两道经典例题，有了例题和板子，才能更好的扩展和延伸，应对不同的场景
二分查找
其实乍一看，直接遍历一遍不就好了吗，但是今天我们的主题是二分查找
所以这一题来学习一下二分的第一个最简单的板子
解法一就是暴力循环找目标值
解法二：
其实核心就是二段性，只要给的数据有二段性，我们就能用二分
最朴素的就是不断的找 mid 然后判断 ，再进到新的区间 ，不断二分
看看这题代码，其实大家应该都会写的，最基础的二分板子
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(target > nums[mid])left = mid + 1;else if( target < nums[mid])right = mid - 1;elsereturn mid;}return -1;}
};
可能觉得二分就这么简单吗？？ 不不不，还有另外两个板子，会有点麻烦
在排序数组中查找元素的第一个和最后一个位置
这题能把另外两个二分的板子完美诠释出来，在做这一题之前，我们先来了解两种情况
前面我们的朴素版本就是 大于 等于 小于 三种情况。
现在我们来想想 左边区间是小于目标值 右边区间是大于等于目标值 两种情况怎么处理
也就是找区间的左端点，如下图：
相比于前面的朴素板子，有很多细节差别
—left 和 right 的更新， 当 x 小于目标值时，那就是左边区间，这时候left——mid的区间都是不满足条件的，因为左边区间都是小于目标值，所以 left 要更新为 mid+1 ，当 x 大于等于目标值时，因为我们右边区间默认是大于等于目标值的区间，我们的 right 如果更新为 mid - 1，有可能当前的mid就是要找寻的点，所以 right 应该更新为 mid
—循环条件 当 left == right 时，就是我们要找的答案，这个时候如果循环条件为 left<=right ,会进入死循环
—mid的取值，看下图，假设就剩下两个值，目标值是left，先用第一种方法 mid 就是 left，这个时候 x >= 目标值，所以right == mid，刚好left 和 right 相等，找到目标值，如果取用第二种方法，取mid为right，这个时候 x >= 目标值，right 和 mid 相等，然后left还是小于right，死循环，所以当我们把区间分成左边完全小于目标值，右边大于等于目标值的时候，就用第一种。
左端点结束了，接下来就是右端点了
也就是左边区间小于等于目标值，右边区间完全大于目标值
需要注意的细节还是
—left 和 right 的更新 ，当 x > 目标值的时候 right更新为 mid - 1，因为右边区间都是大于目标值的， 当 x <= 目标值的时候， left更新为mid，因为左边区间小于等于目标值，可能mid的位置就是目标值
—left < right left 不能等于 right
—还是 mid 的取值问题，再来回到这个图
我们先使用第一种，当right为目标值时，更新 mid 是刚好为 left，这个时候left更新为mid，right还是大于left，陷入死循环，使用第二种的话，更新mid为right，left更新为mid，也就是right，left和right相等，跳出循环，找到目标值。所以当区间分成左区间小于等于，右区间大于时，用第二种取mid
好了，找左右端点我们都学会了这题，也是能稳稳拿下了
题目要求找到目标值的左右端点，那我们来一次找左端点的操作，再来一次右端点的操作就好啦，话不多说，上代码
class Solution
{
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0)return{-1, -1};int begin = 0;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[left] != target) return {-1, -1};begin = left;right = nums.size() - 1;while(left < right) // 找右端点{int mid = left + (right - left + 1) / 2;if(nums[mid] > target)right = mid - 1;elseleft = mid;}return {begin, right};}
};
搜索插入的位置
思路
这题看来就是左区间小于，又区间大于等于，二段性就分好啦
假设插入的坐标是x，那么x左边都是小于目标值的，右区间都是大于等于目标值的
我们可以用查询左端点的板子，直接返回找到的左端点
还有一种特殊情况就是，数据插入在末尾，原本的数据全部小于目标值的，就把这一点处理一下就好了
话不多说，上代码
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;if(nums[mid] < target) // 特殊情况，所有数据都比目标值小left = mid + 1; // 返回right + 1elseright = mid;}if(nums[left] < target)return left + 1;elsereturn right;}
};
x的平方根
思路
本题第一种思路就是暴力枚举就好了，0-x/2区间一个一个枚举，挺简单的思路，就不多赘述了
第二种思路就是二分，我们可以用右端点的板子，设定 i * i <= x为条件，进行二分，最终返回的就是小于等于算数平方根的下标， 话不多说，上代码
class Solution
{
public:int mySqrt(int x) {if(x == 0)return 0;long long right = x / 2, left = 1;while(left < right){long long mid = left + (right - left + 1) / 2; // 查询右端点取中点处理if(mid * mid > (long long)x)right = mid - 1;elseleft = mid;}return left; }
};
其实核心就是找到数据的二段性，然后看情况选择二分查找左端点还是右端点就好啦
山脉数组的峰顶索引
思路
题目的意思是找到山脉的顶峰，第一种思路当然就是暴力查找了，找到最大值就行
第二种思路就是我们可以把山脉分成两份，二段性不就来了嘛，一段单调增，一段单调减
然后根据情况查找左端点或者右端点就好啦
我们把左区间设定为递增到山顶的区间，右区间就是下山的区间
这个时候应该用我们的查询右端点的板子，然后我们的判断条件可以设为 arr[mid] > arr[mid - 1]
话不多说，看代码
class Solution
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1]) left = mid;elseright = mid - 1;}return left;}
};
当然，也可以用查询左端点的板子来写
class Solution
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while(left < right){int mid = left + (right - left) / 2;if(arr[mid] > arr[mid + 1]) right = mid;elseleft = mid + 1;}return left;}
};
其实，核心就是找到二段性，然后再找判断条件
寻找旋转排序数组中的最小值
思路
题目的二段性意思已经写在脸上了，如图
我们直接设定右端点为 x ，然后上查找左端点的板子，这个x用来判断区间条件
就是两步，二段性，区间条件，话不多说，上代码
class Solution
{
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;int x = nums[right];while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > x) // 当前值大于 x 表示在左区间left = mid + 1; // 更新leftelseright = mid;}return nums[left];}
};
总结
二分查找是一种高效的搜索算法，核心在于利用数据的二段性将区间不断二分，快速定位目标。本文通过经典例题解析了三种常见场景的二分应用：
- 基本查找：适用于有序数组，通过比较中间值与目标调整区间，时间复杂度O(logN)。
- 边界查找：
- 左边界：右区间≥目标，循环条件
left<right，mid取左中点，更新策略确保不遗漏可能解。 - 右边界：左区间≤目标，mid取右中点，避免死循环。
- 左边界：右区间≥目标，循环条件
- 特殊场景：如山脉数组峰值、旋转数组最小值，通过分析数据规律（如单调性变化点）构造二段性条件。
关键点：
- 循环条件选择（
left<right或left<=right）。 - mid计算方式（防止溢出）与边界更新策略。
- 处理目标不存在或越界的特殊情况。
掌握二分查找的核心在于理解区间划分逻辑，灵活选择模板，结合问题特点设计判断条件，从而高效解决复杂查找问题
今天的内容就到这里啦，不要走开小编持续更新中~~~
