【基础算法】二分算法深度剖析：从模板到实战，二分查找与二分答案一网打尽
| 🔭 个人主页：散峰而望 |
|---|
《C语言：从基础到进阶》《编程工具的下载和使用》《C语言刷题》《算法竞赛从入门到获奖》《人工智能》《AI Agent》
愿为出海月，不做归山云
🎬博主简介
【基础算法】二分算法深度剖析：从模板到实战，二分查找与二分答案一网打尽
前言
前言
在算法的世界里，二分算法如同一把精准的钥匙，能快速开启有序数据的大门。无论是经典的有序序列查找，还是复杂的“最小值最大”类问题，二分思想都以惊人的效率（O(log n)）化繁为简，成为程序员必须掌握的核心技能。然而，许多初学者在运用二分时常常陷入边界不清、死循环或答案错误的窘境。本文将从二分的本质出发，深入剖析其原理与易错点，提供清晰可靠的模板，并带你走进 STL 中的二分利器。随后，我们将通过“二分查找”与“二分答案”两大实战板块，精选六道经典题目，从“牛可乐和魔法封印”的区间查询，到“跳石头”的最优化决策，一步步拆解题意、推导思路、实现代码。无论你是刚接触二分的新手，还是希望查漏补缺的进阶者，本文都将助你彻底吃透二分算法，让二分成为你解题时的本能反应。
1. 二分算法
1.1 二分算法的相关概念
二分算法是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
二分算法的原理以及模板其实是很简单的，主要的难点在于问题中的各种各样的细节问题。因此，大多数情况下，只是背会二分模板并不能解决题目，还要去处理各种乱七八糟的边界问题。
二分算法的核心：根据中点位置的值，判断最终解集是在左边区域还是在右边区域。如果确定一半区域，可以舍弃另一半区域，在有所求答案的区域内找。
1.2 二分算法的探讨
算法原理：
- 暴力解法：从前往后扫描数组，时间复杂度是 O(N) ，慢就慢在没有利用数组的有序性。
我们发现，假设要查找的数为 6 ，我们可以将这一串数分为两部分，计算中点为 12 ，则将 12 的左边分为小于 12 的区域，右边分为大于 12 的区域。因为 6 比 12 小，故 6 肯定在 12 的左侧区域，这样的话 12 右侧的区域就不用查找了。之后再在 12 的左侧按照以上的方式继续查找。此时我们发现解集中存在二段性，就可以用到二分算法了。
- 二分算法：
二分算法中需要解决两个位置，一个是起始位置，另一个是终止位置。
首先需要更新左右指针的位置：
细节问题：
(1) 查找起始位置：
- while 循环判断需要如何写：
两种写法：while(left < right)和while(left <= right)；
应该选while(left < right)，另外一种写法会造成死循环。 - 求中点的方式：
同样有两种写法：(left + right) / 2和(left + right + 1) / 2；
应该选(left + right) / 2，另外一种写法会造成死循环。
(2) 查找终止位置：
- while 循环判断需要如何写：
两种写法：while(left < right)和while(left <= right)；
应该选while(left < right)，另外一种写法会造成死循环。 - 求中点的方式：
同样有两种写法：(left + right) / 2和(left + right + 1) / 2；
应该选(left + right + 1) / 2，另外一种写法会造成死循环。
classSolution{public: vector<int>searchRange(vector<int>& nums,int target){int n = nums.size();//处理边界情况if(n ==0)return{-1,-1};//求起始位置int left =0, right = n -1;while(left < right){int mid =(left + right)/2;if(nums[mid]>= target) right = mid;else left = mid +1;}//left 或 right 所指位置可能是最终结果if(nums[left]!= target)return{-1,-1};int releft = left;//求终止位置 left =0, right = n -1;while(left < right){int mid =(left + right +1)/2;if(nums[mid]<= target) left = mid;else right = mid -1;}return{releft, left};}};1.3 二分算法模板
这里我们可以整理出来两个二分模板，方便解决前面所提的细节问题，便于以后使用：
// 二分查找区间左端点 int l =1, r = n;while(l < r){int mid =(l + r)/2;if(check(mid)) r = mid;else l = mid +1;}// 二分结束之后可能需要判断是否存在结果 // 二分查找区间右端点 int l =1, r = n;while(l < r){int mid =(l + r +1)/2;if(check(mid)) l = mid;else r = mid -1;}// 二分结束之后可能需要判断是否存在结果check() 是查找函数。为了防止溢出，求中点时可以下面的方式：mid = l + (r - l) / 2
时间复杂度：
每次二分都会去掉一半的查找区域，因此时间复杂度为 O(logN)
1.4 STL 中的二分
头文件：<algorithm>
lower_bound：大于等于 x 的最小元素，返回的是迭代器；时间复杂度：O(logN) ；upper_bound：大于 x 的最小元素，返回的是迭代器。时间复杂度：O(logN) 。
二者均采用二分实现。但是 STL 中的二分查找只能适用于"在有序的数组中查找"，如果是二分答案就不能使用。因此还是需要记忆二分模板。
2. 二分查找
2.1 牛可乐和魔法封印
算法原理：
- 暴力解法：从前往后扫描一遍，时间复杂度 O(n * q) 。
- 二分查找算法模版题，直接上手模版即可。
但是需要注意，有可能并没有这个区间，需要在二分结束之后判断一下。
参考代码：
#include<iostream>usingnamespace std;constint N =1e5+10;int n;int a[N];intbinary_search(int x,int y){//大于等于 x 的最小元素int left =1, right = n;while(left < right){int mid =(left + right)/2;if(a[mid]>= x) right = mid;else left = mid +1;}if(a[left]< x)return0;int tmp = left;//小于等于 y 的最大元素 left =1, right = n;while(left < right){int mid =(left + right +1)/2;if(a[mid]<= y) left = mid;else right = mid -1;}if(a[left]> y)return0;return left - tmp +1;}intmain(){ cin >> n;for(int i =1; i <= n; i++) cin >> a[i];int q; cin >> q;while(q--){int x, y; cin >> x >> y; cout <<binary_search(x, y)<< endl;}return0;}2.2 A-B 数对
算法原理：
由于顺序不影响最终结果，所以可以先把整个数组排序。
- 暴力解法：两层 for 循环，将 A 和 B 选出来，会超时。
由 A - B = C 得：B = A - C ，由于 C 是已知的数，我们可以从前往后枚举所有的 A，然后去前面找有多少个符合要求的 B ，然后找 B 起始终止位置，可以用二分查找。即时间复杂度为 O(nlogn)
这里我们因为已经有序，所以可以使用 STL 中的二分。
- 二分查找：
(1)lower_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k ，然后返回该数组中 >= k 的第一个位置；
(2) upper_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k ，然后返回该数组中 >k 的第一个位置
比如：a=[10,20,20,20,30,40] ，设下标从 1 开始计数，在整个数组中查询 20：
- lower_bound(a+1,a+1+6,20) ，返回 a+2 位置的指针；
- upper_bound(a+1,a+1+6,20)，返回 a+5 位置的指针；
- 然后两个指针相减，就是包含 20 这个数区间的长度。
lower_bound(a+1,a+1+6,20)||| 指针1 指针2 查找数 
【注意】虽然 STL 用起来很爽，但是不要依赖它。因为后续学习「二分答案」的时候，STL 就无法使用了；同时 STL 的使用范围很局限，查询有序序列的时候才有用，数组无序的时候就无法使用。但是我们的二分模板也能在数组无序的时候使用，只要有二段性即可。
参考代码：
#include<iostream>#include<algorithm>usingnamespace std;typedeflonglong LL;constint N =2e5+10;int n, c; LL a[N];intmain(){ cin >> n >> c;for(int i =1; i <= n; i++) cin >> a[i];sort(a +1, a +1+ n);//排序 LL ret =0;//统计多少对 for(int i =2; i <= n; i++){ LL b = a[i]- c; ret +=upper_bound(a +1, a + i, b)-lower_bound(a +1, a + i, b);} cout << ret << endl;return0;}2.3 烦恼的高考志愿
算法原理：
- 利用 set 来解决。
- 排序 + 二分：找出大于等于估分的最小元素的位置和小于等于估分的最大元素
先把学校的录取分数「排序」，然后针对每一个学生的成绩 b ，在「录取分数」中二分出 >= b 的「第一个」位置 pos ，那么差值最小的结果要么在 pos - 1 位置。
取 abs(a[pos]−b) 和 abs(a[pos−1]−b) 两者的最小值。
细节问题：
- 如果所有元素都大于 b 的时候，pos−1 会在 0 下标的位置，有可能结果出错；
- 如果所有元素都小于 b 的时候， pos 会在 n 的位置，此时结果倒不会出错，但是我们要想到这个细节问题，这道题不出错不代表下一道题不出错。
需要设定一下边界，处理越界访问。
参考代码：
#include<iostream>#include<algorithm>usingnamespace std;typedeflonglong LL;constint N =1e5+10;int m, n; LL a[N];intfind(LL x){int left =1, right = m;while(left < right){int mid =(left + right)/2;if(a[mid]>= x) right = mid;else left = mid +1;}return left;}intmain(){ cin >> m >> n;for(int i =1; i <= m; i++) cin >> a[i];sort(a +1, a +1+ m);//处理边界情况 a[0]=-1e7+10; LL ret =0;for(int i =1; i <= n; i++){ LL b; cin >> b;int pos =find(b); ret +=min(abs(a[pos]- b),abs(a[pos -1]- b));} cout << ret << endl;return0;}3. 二分答案
准确来说，应该叫做二分答案 + 判断。
二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果解空间在从小到大的变化过程中，判断答案的结果出现二段性，此时我们就可以「二分」这个解空间，通过「判断」，找出最优解。
3.1 木材加工
算法原理：
设要切成的长度为 x ，能切成的段数为 c 。根据题意，我们可以发现如下性质：
- 当 x 增大的时候，c 在减小。也就是最终要切成的长度越大，能切的段数越少；
- 当 x 减小的时候，c 在增大。也就是最终要切成的长度越小，能切的段数越多。
- 暴力解法：
枚举所有的切割长度 x ，求出在 x 的情况下，能切出多少段 c 。又由上面的性质我们可以优化从 c >= k(设定段数) 开始枚举，但会超时。
- 二分答案：
设最终的要切的长度结果是 ret，则：
- 当 x <= ret 时，c >= k 。也就是要切的长度小于等于最优长度时，最终切出来的段数大于等于 k ；
- 当 x > ret 时，c < k 。也就是要切的长度大于最优长度时，最终切出来的段数小于 k 。
然后用 c = a[i] / x 算出能切的段数。
参考代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =1e5+10; LL n, k; LL a[N];// 当切割⻓度为 x 的时候，最多能切出来多少段intcalc(LL x){ LL cnt =0;for(int i =1; i <= n; i++){ cnt += a[i]/ x;}return cnt;}intmain(){ cin >> n >> k;for(int i =1; i <= n; i++) cin >> a[i]; LL left =0, right =1e8;while(left < right){ LL mid =(left + right +1)/2;if(calc(mid)>= k) left = mid;else right = mid -1;} cout << left << endl;return0;}3.2 砍树
算法原理：
设伐木机的长度为 H ，能得到的木材为 c 。根据题意，我们可以发现如下性质：
- 当 H 增大的时候，c 在减小；
- 当 H 减小的时候，c 在增大。
设最终的要切的高度结果是 ret，则：
- 当 H <= ret 时，c >= M 。也就是伐木机的高度大于等于最优长度时，最终能得到的木材小于等于 M ；
- 当 H > ret 时，c < M 。也就是伐木机的高度小于最优长度时，最终能得到的木材大于 M 。
同时记得算出木材需要用到 c = a[i] - H 。
参考代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =1e6+10; LL n, m; LL a[N];//当伐木机的高度为 x 时，所能获得的木材 LL calc(LL x){ LL ret =0;for(int i =1; i <= n; i++){if(a[i]> x) ret += a[i]- x;}return ret;}intmain(){ cin >> n >> m;for(int i =1; i <= n; i++) cin >> a[i]; LL left =1, right =2e9;while(left < right){ LL mid =(left + right +1)/2;if(calc(mid)>= m) left = mid;else right = mid -1;} cout << left << endl;return0;}3.3 跳石头
算法原理：
设每次跳的最短距离为 x ，移走的石头块数为 c 。根据题意，我们可以发现如下性质：
- 当 x 增大的时候，c 在减小；
- 当 x 减小的时候，c 在增大。
设最终的结果是 ret，则：
- 当 x <= ret 时，c >= M 。也就是要切的长度小于等于最优长度时，最终切出来的段数小于等于 M ；
- 当 x > ret 时，c < M 。也就是要切的长度大于最优长度时，最终切出来的段数大于 M 。
当我们每次二分一个最短距离 x 时，如何算出移走的石头块数 c ？
- 定义前后两个指针 i,j 遍历整个数组，设 i≤j ，每次 j 从 i 的位置开始向后移动；
- 当第一次发现 a[j]−a[i]≥x 时，说明 [i+1,j−1] 之间的石头都可以移走；
- 然后将 i 更新到 j 的位置，继续重复上面两步。
参考代码：
#include<iostream>usingnamespace std;typedeflonglong LL;constint N =5e4+10; LL l, n, m; LL a[N]; LL calc(LL x){ LL ret =0;for(int i =0; i <= n; i++){int j = i +1;while(j <= n && a[j]- a[i]< x) j++; ret += j - i -1; i = j -1;}return ret;}intmain(){ cin >> l >> n >> m;for(int i =1; i <= n; i++) cin >> a[i]; a[n +1]= l; n++; LL left =1, right = l;while(left < right){ LL mid =(left + right +1)/2;if(calc(mid)<= m) left = mid;else right = mid -1;} cout << left << endl;return0;}结语
结语
二分算法，看似简单，实则精妙。从有序序列中的快速定位，到单调场景下的最优解搜索，它用 O(log n) 的效率诠释了“分而治之”的智慧。本文从基础概念出发，剖析了二分的本质与易错点，给出了清晰通用的模板，并借助 STL 工具提升编码效率。在实战环节，我们通过二分查找解决统计类问题（如牛可乐和魔法封印、A-B 数对、高考志愿），又用二分答案攻克了最优化问题的求解（如木材加工、砍树、跳石头）。这些题目不仅巩固了模板的使用，更让读者体会到二分思想在不同场景下的灵活运用。
二分算法是算法竞赛和日常开发中的必备利器，掌握它，你便能在海量数据面前从容不迫，在复杂问题中快速找到答案。但纸上得来终觉浅，绝知此事要躬行——希望你在理解模板和例题后，能主动找更多习题加以练习，让二分成为你解决算法问题的本能反应。愿你在算法的道路上，每一次二分，都离正确答案更近一步。
愿诸君能一起共渡重重浪，终见缛彩遥分地，繁光远缀天。
