一、定义
将搜索空间分成两半，根据某种条件判断目标在哪一半。
二、概念
整数二分：搜索空间是整数（离散），需要考虑边界和终止条件，容易陷入死循环。
浮点数二分：搜索空间是实数（连续），需要设置精度，终止条件通常用区间长度小于eps。
二分查找：通常指在有序数组中查找特定元素，属于最基础的二分应用。
二分答案：用于优化问题，通过二分可能的答案范围，然后检查该答案是否可行，常用于“最小化最大值”或“最大化最小值”等问题。
三、例题
A – B 数对—-属于二分查找
题目描述（题目来源于洛谷）
方法一：暴力求解
思路
)。当n足够大时，会超时！！！所以需要优化时间复杂度。代码
#include<iostream>
#include<algorithm>
using namespace std;
long long n, c;
const int N = 2e5 + 10;
long long a[N];
int main(){
cin>>n>>c;
//输入数据
for(int i = 0; i < n; i++){
cin>>a[i];
}
//使用整数二分进行查找—-a – b = c可以转换为a = b + c
//先将输入的数据进行排序
sort(a, a + n);
//初始化满足条件的对数为0
long long cnt = 0;
//遍历排序后的数组
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(a[i] – a[j] == c){
cnt++;
}
}
}
cout<< cnt <<endl;
return 0;
}
方法二：整数二分
思路
)。代码
#include<iostream>
#include<algorithm>
using namespace std;
long long n, c;
const int N = 2e5 + 10;
long long a[N];
//求目标值的最小的下标
int min_Pos(long long l, long long r, long long b){
while(l < r){
long long mid = (l + r) / 2;
if(a[mid] >= b){
r = mid;
}else{
l = mid + 1;
}
}
return l;
}
//求目标值的最大的下标
int max_Pos(long long l, long long r, long long b){
while(l < r){
long long mid = (l + r + 1) / 2;
if(a[mid] <= b){
l = mid;
}else{
r = mid – 1;
}
}
return l;
}
int main(){
cin>>n>>c;
//输入数据
for(long long i = 0; i < n; i++){
cin>>a[i];
}
//使用整数二分进行查找—-a – b = c可以转换为a = b + c
//先将输入的数据进行排序
sort(a, a + n);
//初始化满足条件的对数为0
long long cnt = 0;
//遍历排序后的数组
for(long i = 0; i < n; i++){
long long b = a[i] – c;
//求b所对应的位置
long long minPos = min_Pos(0, n – 1, b);
long long maxPos = max_Pos(0, n – 1, b);、
//确保真的存在—-求出对数
if(minPos <= maxPos && a[minPos] == b)
cnt += maxPos – minPos + 1;
}
cout<< cnt <<endl;
return 0;
}
牛可乐和魔法封印—-属于二分查找
题目描述（题目来源于牛客网）
方法一：暴力求解
思路
代码
#include<iostream>
using namespace std;
long long n,q;
const int N = 1e5 + 10;
long long a[N];
int main(){
cin>>n;
//输入数据
for(int i = 0; i < n; i++){
cin>>a[i];
}
cin>>q;
//输入x,y
while(q–){
long long x,y,cnt = 0;
cin>>x>>y;
//暴力求解
for(int i = 0; i < n; i++){
if(a[i] >= x && a[i] <= y){
//只要就加1
cnt += 1;
}
}
cout<< cnt <<endl;
}
return 0;
}
方法二：整数二分
思路
代码
#include<iostream>
using namespace std;
long long n,q;
const int N = 1e5 + 10;
long long a[N];
int query_x(long long l, long long r, long long x){
while(l < r){
long long mid = (l + r) / 2;
if(a[mid] >= x){
r = mid;
}else{
l = mid + 1;
}
}
return l;
}
int query_y(long long l, long long r, long long y){
while(l < r){
long long mid = (l + r + 1) / 2;
if(a[mid] > y){
r = mid – 1;
}else{
l = mid;
}
}
return l;
}
int main(){
cin>>n;
//输入数据
for(int i = 0; i < n; i++){
cin>>a[i];
}
cin>>q;
//输入x,y
while(q–){
long long x,y;
cin>>x>>y;
//处理边界值—x大于最大值，y小于最小值
if(x > a[n – 1] || y < a[0]){
cout<<"0"<<endl;
continue;
}
//使用二分求解x和y对应的下标
long long left = query_x(0, n – 1, x);
long long right = query_y(0, n – 1, y);
//保证区间有效
if (left <= right && a[left] >= x && a[right] <= y) {
cout << right – left + 1 << endl;
}else{
cout<<"0"<<endl;
}
}
return 0;
}
数的三次方根—-属于二分查找
题目描述（题目来源于AcWing）
思路（浮点数二分）
代码
#include<iostream>
#include<cstdio>
using namespace std;
double n,l,r;
int main(){
cin>>n;
l = -100, r = 100;
while(r – l > 1e-8){
double mid = (l + r) / 2;
if((mid * mid * mid) >= n){
r = mid;
}else{
l = mid;
}
}
printf("%.6lf\\n",l);
return 0;
}
木材加工—-属于二分答案
题目描述（题目来源于洛谷）
思路（整数二分）
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int L[N];
int n, k;
// 判断长度为 len 时能否切出至少 k 段
bool check(int len) {
//计数器用于记录当前切了几段
long long cnt = 0;
for (int i = 0; i < n; i++) {
cnt += L[i] / len;
if (cnt >= k) return true; // 提前退出，避免溢出
}
return false;
}
int main() {
cin >> n >> k;
//木头的总长度
long long sum = 0;
//初始化最大木头的长度为0
int maxL = 0;
//输入木头的长度——求出最大的木头的长度
for (int i = 0; i < n; i++) {
cin >> L[i];
sum += L[i];
if (L[i] > maxL) maxL = L[i];
}
// 如果总长度小于 k，连 1cm 都切不出
if (sum < k) {
cout << 0 << endl;
return 0;
}
//整数二分—-用于求出可以切的长度
int l = 1, r = maxL;
while (l < r) {
int mid = (l + r + 1) / 2;
//如果可以切
if (check(mid)) {
l = mid;
} else {
r = mid – 1;
}
}
cout << l << endl;
return 0;
}
砍树—-属于二分答案
题目描述（题目来源于洛谷）
方法一：暴力解法
思路
代码
#include<iostream>
using namespace std;
long long n,m;
const int N = 1e6 + 10;
//存储树的高度,砍下的总长度
long long a[N],sum[N];
int main(){
cin>>n>>m;
long long maxL = 0;
//输入每个树的高度
for(int i = 0; i < n; i++){
cin>>a[i];
//求出树的最大高度
if(a[i] > maxL){
maxL = a[i];
}
}
//暴力解法—对于每一个高度（从1到树的最大高度）–遍历每棵树-求出总的砍下的长度
for(int i = 1; i < maxL; i++){
for(int j = 0; j < n; j++){
if(a[j] > i){
sum[i – 1] += a[j] – i;
}
}
}
//把每个高度砍下的长度与M作比较
for(int i = maxL – 1; i >= 0; i–){
if(sum[i] >= m){
cout<< i + 1 <<endl;
break;
}
}
return 0;
}
方法二：整数二分
思路
）。代码
#include<iostream>
using namespace std;
long long n,m;
const int N = 1e6 + 10;
//存储树的高度,砍下的总长度
long long a[N];
bool check(long long h){
//记录总共砍下的长度为sum
long long sum = 0;
//求出当前高度的砍下的长度
for(int i = 0; i < n; i++){
if(a[i] > h){
sum += a[i] – h;
}
}
//判断当前高度是否能够满足（砍下的木材长度大于等于M）
if(sum >= m){
return true;
}else{
return false;
}
}
int main(){
cin>>n>>m;
long long maxL = 0;
//输入每个树的高度
for(int i = 0; i < n; i++){
cin>>a[i];
//求出树的最大高度
if(a[i] > maxL){
maxL = a[i];
}
}
//整数二分(左右边界为0，maxL)
long long l = 0, r = maxL;
while(l < r){
long long mid = (l + r + 1) / 2;
//当前高度可以满足条件
if(check(mid)){
l = mid;
}else{
r = mid – 1;
}
}
cout<< l <<endl;
return 0;
}
四、总结
二分算法的精髓：单调性 + 折半。
注意事项：
-
错误1：忘记排序（或者数据并非有序）。
-
错误2：边界条件处理不当（索引越界）。
-
错误3：死循环（mid 更新不对）。
