详解“二分”系列算法

前言

1.学习建议

网上教二分系列算法的视频或者文章不在少数，每个人对于二分算法的理解都是不一样的，作者不建议小白刚学习二分系列算法就看很多不同的视频或者博客去学习，举个例子，有些教学提供的方法会把left赋值为-1，right赋值为n；而且每个人对于向上取整和向下取整的理解都是不一样的等等；大家都各有各的道理

新手小白看了不同的视频讲解很容易发懵，所以真心建议，找到一两个时长久高质量的视频，或者篇幅长，介绍完整的博客去认真的看，二分系列算法是有一定难度的，遇到看不懂的就去思考或者问问AI

作者看了很多视频讲解还有相关文章，总结出一套好理解的，主流的方法，供大家参考

一.背景介绍

二分法（Binary Search）是一种在有序数组或有序列表中高效查找目标值的算法；通过不断将数组分为两半来缩小搜索范围，时间复杂度为O(logn)，相比线性查找的O(n)效率大幅提升

二分算法的常见应用大概可以分为以下三种：

• 二分查找（查找指定目标值，目标值存在则返回该值索引，不存在则返回-1）
• 二分检索（通常是指给定目标值，让我们寻找大于等于目标值的最小值，或者小于等于目标值的最大值）
• 二分答案（基于二分检索来解决问题的一种算法）

二.本文解决的逻辑问题

1.详解什么时候使用向上取整，什么时候使用向下取整

2.详解while循环结束条件：到底什么时候用小于，什么时候用小于等于

3.详解二分答案的基本思路

三.二分查找

1.源码（附带保姆级注释）

int Search(int arr[], int numsize, int target)
{//针对于二分查找和二分检索，直接无脑写，二分答案另说int left = 0;int right = numsize - 1;//注意：二分查找是要带等号的！！！while (left <= right){	//二分查找，不需要你考虑向下或者向上取整的问题，直接无脑写默认的向下取整//这里解释一下为什么不写 int mid = (left+right)/2，其实这么写逻辑上是对的//但是，如果left和right特别大的时候，可能会导致mid溢出，用我下面的写法就可以避免溢出的问题int mid = left + (right - left) / 2;//无论是二分查找，还是二分检索，都直接无脑写下面的三板斧//因为无非就这三种情况呀，直接把模板打出来，再去具体思考如何处理if判断语句内部的问题if (arr[mid] < target){//如果当前mid对应的值小于目标值，说明什么？//是不是说明mid前面的值，包括mid自己都要比target小，那我还需要把left移动到mid的当前位置吗？//不需要啊哥们，你问问自己，你要找的数字是不是target？//你当前的mid对应的数组中的值都比target小了，是不是说明当前mid对应的数组中的值，也不是我们要找的值？//但是我们无法确定，mid的下一个位置，mid+1对应的数组中的值是不是等于target//所以我们直接把left移动到mid+1的位置left = mid + 1;}else if (arr[mid] > target){	//如果说当前mid对应的数组中的值大于目标值，说明什么？//是不是说明mid后面的值，包括mid自己对应的值都要比target大，所以跟上面left的移动方式同理啊//我们直接把right指针移动到mid的上一个位置mid-1就好了right = mid - 1;}else if (arr[mid] == target){//我们要执行的是二分查找，所以mid对应的数组中的值一旦等于target，我们直接返回mid就好了return mid;}}//没找到就返回-1呗return -1;
}

四.二分检索

1.寻找满足条件的最小值（采用向下取整方法）

问题：在一个升序数组 {1, 3, 5, 7, 9} 中，找到第一个大于等于 5 的元素

//向下取整方法，找到第一个大于等于target的元素
int fun1(int arr[], int numsize,int target)
{	//针对于二分查找和二分检索，直接无脑写，二分答案另说int left = 0;int right = numsize - 1;//注意：二分检索不带等号！！！while (left < right){	//使用向下取整方法int mid = left + (right - left) / 2;//找到第一个大于等于target的元素//无论是二分查找，还是二分检索，都直接无脑写下面的三板斧//因为无非就这三种情况呀，直接把模板打出来，再去具体思考如何处理if判断语句内部的问题if (arr[mid] < target){	//如果当前mid对应的值小于target，我可以确定的是mid及mid前面的元素都比target要小//所以我可以直接把left移动到mid+1的位置left = mid+1;}else if (arr[mid] > target){	//如果当前mid对应的值大于target，我可以确定的是mid及mid后面的值都比target大//但是mid前面的值是否还有比target大的呢（如果存在就说明当前mid不是目标值），我不清楚//所以说我只能把right移动到mid的位置right = mid;}else if(arr[mid] == target){	//如果当前mid对应的值等于target，我可以确定的是mid及mid后面的值都大于等于target//但是我无法确认mid之前是否还存在等于target的值，所以我们只能把right移动到mid的位置right = mid;}}//这里return left或者right都可以//return left;return right;
}

2.寻找满足条件的最大值（采用向上取整方法）

问题：在一个升序数组 {1, 3, 5, 7, 9} 中，找到最后一个小于等于 5 的元素

//向上取整方法，找到最后一个小于等于target的元素
int fun2(int arr[], int numsize, int target)
{	//针对于二分查找和二分检索，直接无脑写，二分答案另说int left = 0;int right = numsize - 1;//注意：二分检索不带等号！！！while (left < right){//使用向上取整方法int mid = left + (right - left + 1) / 2;//找到最后一个小于等于target的元素//无论是二分查找，还是二分检索，都直接无脑写下面的三板斧//因为无非就这三种情况呀，直接把模板打出来，再去具体思考如何处理if判断语句内部的问题if (arr[mid] < target){	//如果当前mid对应的值小于target，我可以确定的是mid及mid以前的值都比target小//但是mid的下一个值是否还存在比target要小的值呢（如果存在就说明当前mid不是目标值），我不知道//所以我们可只能把left移动到mid的位置left = mid;}else if (arr[mid] > target){//如果当前mid对应的值大于target，我可以确定的是mid及mid以后的值都比target大//所以直接把right移动到mid的前一个位置（mid-1）right = mid - 1;}else if (arr[mid] == target){	//如果当前mid对应的值等于target，那就说明mid及mid之前的值都小于等于target//但是我无法确认mid之后是否还存在等于target的值，所以我们只能把left移动到mid的位置left = mid;}}//这里return left或者right都可以//return left;return right;
}

五.解释什么时候使用向上取整，什么时候使用向下取整

向下取整

适用于寻找最小值的情况，例如第一个大于等于某个值的元素
适用于 right = mid 的更新规则

向上取整

适用于寻找最大值的情况，例如最后一个小于等于某个值的元素
适用于 left = mid 的更新规则
如果你使用错误，程序在执行某些用例的时候会出现死循环情况

六.解释while循环结束条件：到底什么时候用小于，什么时候用小于等于

二分查找为什么使用left<=right

这是因为二分查找的目标是在有序数组中精确查找某个目标值是否存在

• 二分查找需要确保所有可能的候选值都被检查
• 如果使用 left < right，当 left == right 时，会跳过最后一个元素的检查，可能导致漏判
• 当 left > right 时，说明搜索范围已经无效，目标值不存在

二分检索为什么使用left<right

这是因为二分检索的目标是在有序数组中寻找满足条件的最大值或最小值

• 二分法查找最大/最小值的核心是逐步缩小搜索范围，直到 left == right，此时 left 或 right 就是最终答案
• 如果使用 left <= right，可能会导致死循环（例如在 left == right 时，mid 永远等于 left，无法缩小范围）
• 当 left == right 时，搜索范围已经缩小到单个值，这个值就是答案，无需继续循环

七.解释二分检索中返回值为什么return right 或者 left 都可以

在二分检索中，循环结束时，right和left是处于相同位置的，所以返回他们哪个都可以，这里可以联系到while循环的结束条件去理解

八.二分查找和二分检索的本质区别

在二分查找中；假如我们要找到5这个数字，5这个数字要么在数组中，被找到，要么不在数组中，找不到
在二分检索中；假如我们要找到大于5的最小值，5这个数字可以不在数组中
这就是二分检索和二分查找的本质区别！！！

九.二分答案

1.解题步骤

• 证明问题单调性所在
• 确定问题单调区间的上下界
• 设计check函数，方便每一次二分求解的时候，判断当前值是否满足指定的限定条件
• 在单调区间上下界之内二分答案（通过循环实现二分）：若当前值不行缩小一半的查询区间，继续查询；若当前值可行，为候选解，但继续缩小一半的空间求更优解

2.实战演示

题目描述：

农夫约翰有 n 个牛舍，它们的位置排列在一条直线上，坐标分别为 x₁, x₂, …, xₙ。他需要将 m 头牛分配到这些牛舍中，且每头牛必须放在不同的牛舍。为了确保牛之间有足够的活动空间，约翰希望使得任意两头相邻牛之间的最小距离尽可能大。请你帮助他找到这个最大的最小距离

输入格式：​

第一行包含两个整数 n 和 m（2 ≤ n ≤ 1e5，2 ≤ m ≤ n），分别表示牛舍数量和牛的数量
第二行包含 n 个整数 x₁, x₂, …, xₙ（0 ≤ xᵢ ≤ 1e9），表示牛舍的坐标。数据保证坐标按升序排列

输出格式：​

输出一个整数，表示最大的最小距离

示例输入：​

5 3
1 2 4 8 9

示例输出：​

3

本题思路

1. 确定我们要求的值，“相邻两牛之间最短距离的最大值”
2. check函数设计的原理是：检查是否能以至少 d 的距离放置至少 m 头牛
3. 相邻两牛之间的距离可以看作一个升序数组，也就是说要找到这个升序数组中，合法（可以通过check检验）的最大值
4. 既然是求取最大值，我们就可以通过二分检索中向上取整的方法设计函数

解题代码：

check函数代码：

// 检查是否能以至少 d 的距离放置至少 m 头牛
bool check(int d, int m, const vector<int>& arr) {int cnt = 1;                // 已放置的牛的数量（第一个牛舍必须放）int prev = arr[0];          // 上一头牛的位置for (int i = 1; i < arr.size(); ++i) {if (arr[i] - prev >= d) {cnt++;prev = arr[i];if (cnt >= m) {     // 提前终止条件：已满足数量要求return true;}}}return cnt >= m;           // 最终是否满足条件
}

二分答案主干代码：

int fun_asr(const vector<int>& arr, int m) {int left = 1;int right = arr.back() - arr[0];while (left < right) {int mid = (left + right + 1) / 2;  // 向上取整if (check(mid, m, arr)) {          // 当前距离可行，尝试更大的值left = mid;}else {                           // 不可行，缩小右边界right = mid - 1;}}return left;  // 最终 left == right，即为答案
}

完整的代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;//二分答案// 检查是否能以至少 d 的距离放置至少 m 头牛
bool check(int d, int m, const vector<int>& arr) {int cnt = 1;                // 已放置的牛的数量（第一个牛舍必须放）int prev = arr[0];          // 上一头牛的位置for (int i = 1; i < arr.size(); ++i) {if (arr[i] - prev >= d) {cnt++;prev = arr[i];if (cnt >= m) {     // 提前终止条件：已满足数量要求return true;}}}return cnt >= m;           // 最终是否满足条件
}int fun_asr(const vector<int>& arr, int m) {int left = 1;int right = arr.back() - arr[0]; //极限思想，相邻两头牛的最大距离不会超过第一个牛舍到最后一个牛舍的距离while (left < right) {int mid = (left + right + 1) / 2;  // 向上取整if (check(mid, m, arr)) {          // 当前距离可行，尝试更大的值left = mid;}else {                           // 不可行，缩小右边界right = mid - 1;}}return left;  // 最终 left == right，即为答案
}int main() {// 加速输入输出ios::sync_with_stdio(false);cin.tie(nullptr);// 读取输入int n, m;cin >> n >> m;vector<int> arr(n);for (int i = 0; i < n; ++i) {cin >> arr[i];}// 必须先将牛舍坐标排序（题目虽说明输入有序，但实践中建议强制排序）sort(arr.begin(), arr.end());// 计算并输出结果cout << fun_asr(arr, m) << endl;return 0;
}

3.作者对二分答案的理解

• 二分答案的题目都可以用二分检索的方法解决，题目要求我们求取最大值，我们就用二分检索的方式结合向上取整解决问题，题目要求我们求取最小值，我们就用二分检索的方式向下取整解决问题

十.总结

建议吃透本文源码后多练习几道算法题，即使是作者本人，对于一些细节的理解也不是很熟练，也要勤加练习