蓝桥杯：C++二分算法
在基本算法中，二分法的应用非常广泛，它是一种思路简单、编程容易、效率极高的算法。蓝桥杯软件类大赛中需要应用二分法的题目很常见。
二分法有整数二分和实数二分两种应用场景
二分法的概念
二分法的概念很简单，每次把搜索范围缩小为上一次的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～100int 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的测试数据 ，最后两个测试数据错了，暂时不知道什么原因
}整数二分法求解：
#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+Rif(check(mid)) L=mid; //新的搜索区间是右半部分，R不变，调整L=midelse R=mid-1; //新的搜索区间是左半部分，L不变，调整R=mid–1}cout << L;//第二种写法：/* while(L<R) {int mid=(L+R) / 2; //除以2，向左取整 不会整数溢出，直接L+Rif(check(mid)) L=mid+1; //新的搜索区间是右半部分，R不变，更新L=mid+1else R=mid; //新的搜索区间是左半部分，L不变，更新R=mid}cout << L-1; */return 0;
}实数二分
与整数二分相比，实数二分的编程就容易多了，不用考虑整数的取整问题。实数二分的模板代码如下。
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;
}