【C++】二分查找--超详细图解（小白一看就懂！！！）
【C++】二分查找--超详细图解（小白一看就懂！！！）
目录
一、前言
二、二分思想
✨算法引出
✨算法形成的条件
三、二分查找详解
✨写法1：左闭右闭
🥝正确的写法（正确演示）
🍍错误的写法 (错误演示)
✨写法2：左闭右开
🍎正确的写法（正确演示）
🍐错误的写法 (错误演示)
✨ 总结
四、常考面试题
💦搜索插入位置
💦在排序数组中查找元素的第一个和最后一个位置
💦x的平方根
💦有效的完全平方数
五、共勉
一、前言
二分法的思想虽然容易理解，但在处理边界问题时，很多人往往只能靠记忆模板，一旦忘记模板就容易陷入混乱。因此，本文将详细解释二分法的左闭右闭区间和左闭右开区间两种写法，并通过正反例演示，帮助读者深入理解边界处理问题。
二、二分思想
✨算法引出
想象一下，小明从图书馆借了N本书，出图书馆时警报响了。保安通过二分查找的方式，仅用logN次就找到了未登记的书。这个故事说明了二分查找需要满足两个条件：
- 查找的内容需要是有序的
- 查找的数量只能是一个
例如，在一个有序且无重复元素的数组中查找某个元素的位置，就可以使用二分查找。
✨算法形成的条件
二分查找需要满足以下条件：
- 数组必须是有序的
- 数组中不能有重复元素（至少在查找单一目标时）
二分查找的核心是确定查找范围，主要涉及左右区间的开闭问题。主要有两种方式：
- 左闭右闭：[left, right]
- 左闭右开：[left, right)
三、二分查找详解
我们通过一道二分查找题目来深入了解其细节。
✨写法1：左闭右闭
🍠正确的写法（正确演示）
第一种写法是每次查找的区间在[left, right]（左闭右闭区间）。根据查找区间的定义，代码应该这样写：
- 循环条件使用while(left <= right)，因为当left == right时，区间仍然有效
- 如果nums[middle] > target，right应该赋值为middle - 1，因为当前的nums[middle]一定不是target，需要排除
代码如下：
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0; // 下标从0开始
int right = nums.size() - 1; // 定义target在左闭右闭的区间里[left,right]
while (left <= right) // 当left == right时，区间[left, right]仍然有效
{
int mid = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2；int会向下取整
if (nums[mid] > target)
{
right = mid - 1; // target 在左区间，所以[left, middle - 1]
}
else if (nums[mid] < target) // target 在右区间，所以[middle + 1, right]
{
left = mid + 1;
}
else // nums[middle] == target
{
return mid; // 数组中找到目标值，直接返回下标
}
}
return -1; // 未找到目标值
}
};
图例解析：
假设需要在数组中查找33：
初始化left和right，计算middle的值
比较nums[middle]和target的值
根据比较结果更新left或right
继续循环直到找到目标值
🍍错误的写法(错误演示)
如果将循环条件修改为while(left < right)，会出现死循环：
初始化数组，计算middle的值
根据比较结果更新left或right
继续计算middle的值
更新left或right
最终导致死循环
✨写法2：左闭右开
🍎正确的写法（正确演示）
第二种写法是每次查找的区间在[left, right)（左闭右开区间）。根据区间的定义，条件控制应该如下：
- 循环条件使用while(left < right)
- 如果nums[middle] > target，right赋值为middle，因为当前的nums[middle]是大于target的，不符合条件，不能取到middle
代码如下：
class Solution {
public:
int search(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
while (left < right) // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
{
int mid = left + ((right - left) >> 1); // >>右移运算符 向右移动一位相当于除2
if (nums[mid] > target)
{
right = mid; // target 在左区间，在[left, middle)中
}
else if (nums[mid] < target)
{
left = mid + 1; // target 在右区间，在[middle + 1, right)中
}
else // nums[middle] == target
{
return mid; // 数组中找到目标值，直接返回下标
}
}
return -1; // 未找到目标值
}
};
图列解析如下：
初始化left和right的值，计算middle的值
比较nums[middle]和target的大小
更新right的值
继续计算middle的值
更新right的值
比较nums[middle]和target的大小关系
更新left的值
成功找到target
🍐错误的写法(错误演示)
如果将循环条件修改为while(left <= right)，会出现死循环：
初始化数组，计算middle的值
比较nums[middle]和target的大小关系
更新left的值
比较nums[middle]和target的大小关系
更新right的值
比较nums[middle]和target的大小关系
更新right的值
最终导致死循环
✨ 总结
二分法最重要的两个点，就是循环条件和后续的区间赋值问题。因为两者是相互联系、相互影响的，所以就需要两者统一。如果两者不统一，就会出现问题。所以循环条件和赋值问题必须统一，也就是循环不变量。
见到数组的题，首先要看是否有顺序，如果有，可以根据题意考虑是否合适使用二分查找。然后在写二分查找时，要对区间定义想清楚，区间的定义就是不变量，建议多画画图。要在二分查找过程中保持不变量，就是要用while寻找每一次边界的处理，都要坚持根据区间的定义来操作，这就是循环不变量的规则。写二分法，区间定义要想清楚，一般有两种，左闭右闭[left, right]和左闭右开[left, right)。
四、常考面试题
💦搜索插入位置
链接：35. 搜索插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target)
{
// 双指针
int left = 0,right = nums.size();
int mid = 0;
// 左闭右开
while(left<right)
{
mid = left+((right-left)>>1);
if(nums[mid]>target)
{
right = mid;
}
else if(nums[mid]<target)
{
left = mid+1;
}
else{
return mid;
}
}
return left;
}
};
💦在排序数组中查找元素的第一个和最后一个位置
链接：34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
// 二分查找
int binarysearch(vector<int>& nums, float target)
{
int left = 0;
int right = nums.size();
while(left<right)
{
int mid = left+(right-left)/2;
if(nums[mid]>target)
{
right = mid;
}
else if(nums[mid]<target)
{
left = mid+1;
}
// 这里不能等于 mid
}
// 返回 小于最近整数的前一个位置
return left;
}
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int> v(2,-1);
// 两次二分
int strat = binarysearch(nums,target-0.5);
int end = binarysearch(nums,target+0.5);
// 没找到
if(strat==end)
{
return v;
}
else
{
v[0] = strat;
v[1] = end-1;
}
return v;
}
};
💦x的平方根
链接：69. x 的平方根
class Solution {
public:
int mySqrt(int x)
{
// 1 和 0 的算数平方根为自身
if(x<=1)
{
return x;
}
// 左闭右开 [1,x/2+1)
// 所有大于等于4的数，其算数平方根小于等于它的一半
int left = 1;
int right = x/2+1;
while(left<right)
{
int mid = left+((right-left)>>1);
if((long)mid*mid<x)
{
left = mid+1;
}
else if((long)mid*mid>x)
{
right = mid;
}
else
{
return mid;
}
}
return left-1;
}
};
💦有效的完全平方数
链接：367. 有效的完全平方数
class Solution {
public:
bool isPerfectSquare(int num)
{
if(num<=1)
{
return true;
}
int left = 1;
int right = num/2+1;
while(left<right)
{
int mid = left+((right-left)>>1);
if((long)mid*mid < num)
{
left = mid+1;
}
else if((long)mid*mid > num)
{
right = mid;
}
else
{
return true;
}
}
return false;
}
};
五、共勉
以上就是对二分查找的理解，如果有不懂或发现问题的地方，请在评论区指出。同时，还会继续更新对C/C++的理解，敬请关注。