二分思想分为两类：
整数域上的二分
实数域上的二分
一、整数域上的二分，分三步 (其中mid最好是>>1 而不是/2, 因为>>1 是向下取整，而/2是向0取整，在负数时很有用)
①通过分析具体问题，确定左右半段哪一个是可行区间，以及mid归属那一半段。
②根据分析结果，选择“r=mid, l=mid+1, mid=(l+r)>>1” 和 “l=mid, r=mid-1, mid=(l+r+1)>>1”两个配套形式之一。
③二分终止条件是l==r, 该值就是答案所在位置。
（一定要注意区间的选择，区间[0,n] 和 [1,n+1] 这两个不能够乱用 ，0和n+1 都是越界下标，只有在特定情境下若没有找到才会等于越界下标）
！例题！磁铁了解一下
输入：5 3 输出：3
1
2
8
4
9
二分法求最大的最小值：二分搜索判断距离
#include<bits/stdc++.h> #define INF 0x3f3f3f3f; using namespace std; int a[100005]; int n,m; bool jude(int d) { int last=0; //last 表示第一个磁铁放置的位置 for(int i = 1; i < m; i++){ int now=last+1; while(now<n&&a[now]-a[last]<d)now++;//now表示下一个磁铁放置的位置 if(now==n)return false;//如果不满足，返回false last=now; //记录该磁铁放置的位置 } return true; } int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&a[i]); sort(a,a+n); //从小到大排序 int l=0,r=INF; while(r-l>1){ //二分搜索 int mid=(l+r)/2; if(jude(mid))l=mid;//如果该距离满足条件，则距离+ else r=mid;//否则，距离- } printf("%d\n",l); return 0; }
// 在单调递增序列a中查找>=x的数中的最小的一个： while(l<r) { int mid=(l+r)>>1; if(a[mid]>=x) r=mid; else l=mid+1; } return a[l]; // 在单调递增序列a中查找<=x的数中的最大的一个： while(l<r) { int mid=(r+l+1)>>1; if(a[mid]<=x) l=mid; else r=mid-1; } return a[l];
二、实数域上的二分(重点是精度的确定)
重要的是确定好所需的精度eps，以l+eps<r为循环条件，每次根据在mid 上的判定选择r=mid 或 l=mid分支之一即可，一般需要保留k位小数是，则取eps=10^-(k+2)
！例题！二分面包了解一下
题目背景
mxj买了n个长条形面包，但是他们的长度不完全相同，为了让俱乐部的每个孩子得到长度相同并且尽可能能长的面包，mxj开始敲起了代码，计算如何切面包。
题目描述
这n个面包的长度至少为1，俱乐部中现在有k个人,现在你需要计算出如何把这n块面包切成k块，并使这k块面包的长度最大？保证答案有解，答案保留两位小数。
输入格式：
第一行，两个整数n,k,意义如上
第二行有n个数，表示每条面包的长度Li,每个输入都有两位小数.
输出格式：
输出面包的最大长度(保留2位小数)
输入输出样例
输入样例#1：
4 11
8.02
7.43
4.57
5.39
输出样例#1：
2.01
说明
1<=n,k<=10000
1<=Li<=100000
没读懂这道题，嘤嘤嘤，我一开始理所应当的认为就加一起平分呗，哈哈哈，可能会有人吃好几个面包的一点，xswl，这居然是实数域上的二分
#include<bits/stdc++.h> using namespace std; const int N=1e4+5; int n,k; double l[N]; int main(void) { cin>>n>>k; double maxv=-1; for(int i = 0 ; i < n ; i++) { scanf("%lf",&l[i]); if(l[i] > maxv) maxv=l[i];//选取整个数组中最大的长度作为右边界，左边界可以选择最小的，也可以选择0，这个代码选择零 } double x = 0 , y = maxv , mid;//左边界，右边界，猜想值 while(y - x > 0.00001)//注意精度 { double sum=0; mid=(x + y) / 2; for(int i = 0 ; i < n ; i++) sum = sum + (int)(l[i] / mid);//结果向下取整~我们得到的结果就是所有面包按照这个猜想值分面包能分出多少块面包。 if(sum>=k) x=mid; else y=mid; /* 这个值sum大于等于k就代表我们分的多了，也就是每一块面包的长度太小了，这个时候我们将左边界赋值为这个猜想值；反之，我们将右边界赋值为这个猜想值。 */ } printf("%.2f\n",mid); }
p.s.:有时精度不容易确定或者表示，就干脆采用循环固定次数的二分方法，也是一种相当不错的策略。这种方法得到的结果的精度通常比设置eps更高。
//eg: for(int i=0;i<100;i++) { double mid=(l+r)/2; if(calc(mid)) r=mid;else l=mid; }
