在基本算法中，二分法的应用非常广泛，它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。
二分法有整数二分和实数二分两种应用场景
二分法的概念
二分法的概念很简单，每次把搜索范围缩小为上一次的1/2，直到找到答案为止。
二分法的效率很高，只需计算log(n)次。
下面介绍二分法的模板代码bin_search()函数：
我们用猜数字的例子，先给数组初始化，然后定义你要猜的数，用二分法效率高。
对于二分法的讲解非常细致，都在注释中。
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int bin_search(int *a, int n, int x) { //在数组a中查找数字x，返回位置
int left = 0, right = n; //left 通常初始化为 0，表示搜索范围的左边界是数组的第一个元素；right通常初始化为 n（数组的长度），表示搜索范围的右边界是数组的最后一个元素的下一个位置。
while (left < right) {
int mid = left+(right-left)/2; //mid的标准写法，建议这样写，不能用(left+right)/2,有可能会整数溢出的。
if (a[mid] >= x) right = mid; //x小，在左边，把右边的一半砍掉，这里就不用加1了，我们本身就是大于等于x。
else left = mid+1; //加1的原因是我们要跳过 a[mid] 这个元素，因为它小于 x，我们要的是等于x的元素
cout<<a[mid]<< " "; //输出猜数的过程 如果你想省略过程，可以注释掉这一行的输出语句。
}
return left; //返回left所在的索引，不要牵扯到right，避免混淆，right一开始是索引的下一个位置。
}
int main() {
int n = 100;
for(int i=0; i<n; i++) a[i]=i+1; //赋值，数字1～100
int test = 54; //猜54这个数
int pos = bin_search(a,n,test);
cout<<"\n"<<"test="<<a[pos];
}bin_search()有3个重要点：区间左端点left、区间右端点right、二分的中位数mid。每次把区间缩小一半，把left或right移动到mid；直到left = right为止，即找到答案所处的位置。
二分法的作用：
二分法可以把一个长度为n的有序序列上O(n)的查找时间优化到O(logn)。
注意应用二分法的前提：序列是有序的，按从小到大或从大到小排序。
无序的序列无法二分，如果是无序的序列，则应该先排序再对其进行二分，先排序再二分，排序的复杂度是O(nlog2(n))，二分的复杂度是O(log2(n))。排序加二分的总复杂度是O(nlog2(n))。如果使用暴力法，直接在无序的n个数里面查找，最多查找n次，复杂度是O(n)的，比先排序再二分快。如果不是查找一个数，而是查找m个数，那么先排序再做m次二分的计算复杂度是O(nlog2(n)+ mlog2(n))，而暴力法的复杂度是O(mn)，此时二分法远好于暴力法。
整数二分
在单调递增序列中查找x或者x的后继：
前面介绍的bin_search()函数就是“在单调递增序列中查找x或者x的后继”的模板代码。
二分函数都是一摸一样的，测试数据可以改一下，看看能不能查找后继：
int main() {
int n = 100;
for(int i=0; i<n; i++) a[i]=2*i+2; //赋值，数字2～200，偶数
int test = 55; //查找55或55的后继
int pos = bin_search(a,n,test);
cout<<"test="<<a[pos];//56 55没有，只能找56了。
}在单调递增序列中查找x或者x的前驱：
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int bin_search2(int *a, int n, int x) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right-left + 1)/2 ; //+1是为了确保在 left 和 right 之间的元素数量是奇数时，mid 会指向中间元素；当元素数量是偶数时，mid 会指向中间两个元素的右侧那个元素。
//这样做的原因是，我们希望在存在重复元素时，mid 尽可能向右偏移，从而找到最右侧的那个等于或小于 x 的元素。
if (a[mid] <= x) left = mid;
else right = mid - 1;
}
return left;
}
int main() {
int n = 100;
for(int i=0; i<n; i++) a[i]=2*i+2; //赋值，数字2～200,偶数
int test = 55; //查找55或55的前驱
int pos = bin_search2(a,n,test);
cout<<"test="<<a[pos]; //54
}整数二分例题
例题1.分巧克力
2017年（第八届）省赛，lanqiaoOJ题号99
先试试暴力法：从边长为1开始到最大边长d，每个值都试一遍，一直试到刚好够分的最大边长为止。编程思路：边长初始值d = 1，然后d = 2、3、4……一个一个地试 。
代码：
#include<bits/stdc++.h>
using namespace std;
int h[100010],w[100010];//多申请10个空间
int n,k;
bool check(int d) { //检查够不够分
int num=0;
for(int i=0; i<n; i++) num += (h[i]/d)*(w[i]/d);//假如，将6×5的巧克力的长边（6个单位）和宽边（5个单位）分别除以2×2的小正方形的边长（2个单位）。
//这样可以得到长边可以切出3个2×2的巧克力，宽边可以切出2个2×2的巧克力。
//接着，将长边和宽边切出的巧克力块数相乘，即3（长边切出的块数）× 2（宽边切出的块数）= 6。所以，一块6×5的巧克力可以切出6块2×2的巧克力。
if(num>=k) return true; //够分
else return false; //不够分
}
int main() {
cin >>n>>k;
for(int i=0; i<n; i++) cin>>h[i]>>w[i]; //长宽各自存在各自的数组中
int d=1; //正方形边长
while(1) {
if(check(d)) d++; //边长从1开始，一个一个地试
else break;
}
cout << d-1;
return 0; //暴力求解只能过75的测试数据 ，最后两个测试数据错了，暂时不知道什么原因
}整数二分法求解：文章来源：https://www.toymoban.com/news/detail-826170.html
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N=100010;
int h[N],w[N];
bool check(int d) {
int num=0;
for(int i=0; i<n; i++) num += (h[i]/d)*(w[i]/d);
if(num>=k) return true; //够分
else return false; //不够分
}
int main() {
cin >> n >> k;
for(int i=0; i<n; i++) cin>>h[i]>>w[i];
int L=1, R=N; //R的初值是100010
//第一种写法：
while(L<R) {
int mid=(L+R+1) / 2; //除以2，向右取整 不会整数溢出，直接L+R
if(check(mid)) L=mid; //新的搜索区间是右半部分，R不变，调整L=mid
else R=mid-1; //新的搜索区间是左半部分，L不变，调整R=mid–1
}
cout << L;
//第二种写法：
/* while(L<R) {
int mid=(L+R) / 2; //除以2，向左取整 不会整数溢出，直接L+R
if(check(mid)) L=mid+1; //新的搜索区间是右半部分，R不变，更新L=mid+1
else R=mid; //新的搜索区间是左半部分，L不变，更新R=mid
}
cout << L-1; */
return 0;
}实数二分
与整数二分相比，实数二分的编程就容易多了，不用考虑整数的取整问题。实数二分的模板代码如下。文章来源地址https://www.toymoban.com/news/detail-826170.html
const double eps = 1e-7; //精度。
while(right - left > eps) {
double mid = left+(right-left)/2;
if (check(mid)) right = mid; //判定，然后继续二分，check(mid)为true执行此语句
else left = mid;
}到了这里，关于蓝桥杯：C++二分算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
