当前位置：首页 > article >正文

基础算法——二分（C语言版）

article 2025/9/11 8:21:01

二分法的用途
用来查找一个区间中满足某种性质的边界点，如：大于某数的最小值、小于某数的最大值
这个性质可以将区间划分为两段
（区间有单调性一定可以用二分查找区间中的某个数，但可以二分不一定具有单调性）
二分思想
通过不断折半查找区间，缩小查找范围，直到找到所求值
代码实现步骤：
（1）确定二分区间 ：确定要找的答案所在的区间，然后循环（2）、（3）、（4）操作
（2）找中点：找到区间中点mid
（3）选check：写一个check函数，判断mid是否满足边界点所在性质
（4）更区间：看边界点在mid左侧区间还是右侧区间，更新区间端点，保证分界点一定在新区间中
二分算法分类：整数二分、浮点数二分
整数二分
两个模板¹：

//区间[l, r]被划分成[l, mid]和[mid+1, r]时使用：
int bsearch_1(int l, int r)
{while(l<r){int mid=(l+r)/2;if(check(mid))  r=mid; //check()判断mid是否满足性质else l=mid+1;}return l;   //最终l与r相等，所以返回l,r都可以
}//区间[l, r]被划分成[l, mid-1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while(l<r){int mid=(l+r+1)/2;    //由于C语言向下取整，如果不+1，当区间中只有两个数时中点不断向下取整，导致区间无法继续更新，出现死循环if(check(mid)) l=mid;  //如：当l=r-1且check（mid）为真时else r=mid-1;}return l;
}

应用例题：数的范围
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。

输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
1≤n≤100000

1≤q≤10000

1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5

输出样例：
3 4
5 5
-1 -1

#include<stdio.h>
#define N 100000int main(void)
{int q[N], n, m, i, x;scanf("%d %d", &n, &m);for(i=0; i<n; i++) scanf("%d", &q[i]);while(m--)    //进行m次查询{scanf("%d", &x);  //读入要查询的数x//用第一个模板查询左边界int l=0, r=n-1;     //初始化查找区间while(l<r){int mid = (l+r)/2;if(q[mid]>=x) r=mid; //这里是r=mid，所以不用+1else l=mid+1;}if(q[l] != x) printf("-1");else printf("%d", l);//用第二个模板查找右边界l=0, r=n-1;     //初始化查找区间while(l<r){int mid = (l+r+1)/2;if(q[mid]<=x) l=mid;  //这里是l=mid，所以要+1else r=mid-1;}if(q[l] != x) printf(" -1\n");else printf(" %d\n", l);}return 0;
}

关于整数二分出现两个模板的原因：
首先由于整数二分的区间是离散的，所以区间的边界有两个。
然后我们在二分时需要找到区间中点，根据中点是否在答案所在区间以及答案是哪个边界分情况更新区间。这样我们就要分四种情况。
而这两个模板分别包含了两种情况，每个模板都假定二分的中点一定在答案所在区间。

浮点数二分
模板¹：

#define 1e-6
double bsearch_3(double l, double r)
{while(r-l>EPS){double mid = (l+r)/2;if(check(mid)) r=mid;else l=mid;}return l;
}

应用例题：数的三次方根
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
−10000≤n≤10000
输入样例：
1000.00
输出样例：
10.000000

#include<stdio.h>
#include<math.h>
#define EPS 1e-8int main(void)
{double x, mid;scanf("%lf", &x);double l=0, r=fabs(x);while(r-l>EPS){mid = (l+r)/2;                   //浮点数二分无需考虑边界问题if(mid*mid*mid>fabs(x)) r=mid;  //如果mid的三次方大于x更新右端点else l=mid;                    //否则更新左端点}if(x<0) printf("%.6f", -l);else printf("%.6f", l);return 0;
}