整数二分与浮点数二分
二分的数学思想：一、整数二分1、思路2、模板C++版 二、浮点数二分1、思路：2、代码：C++版C
二分的数学思想：
二分的数学思想其实就是极限，我们通过取中点的方式，不断地缩小答案所在的区间，让这个区间不断地逼近答案，类似于我们在高数中所学的极限：
一、整数二分
1、思路
我们假设想要寻找上述数轴中的左右边界。
我们先看左边界中的A点，不看B点。我们仔细观察一下A点处符合的性质。
根据上图中的性质，我们就可以开始写二分了。
根据刚刚的描述二分是一个不断逼近地过程，可以理解为两侧端点不断靠近的过程。
将左端点的下标设为 l l l，右端点下标设为 r r r，中间点的下标设为 m i d mid mid， m i d = ( l + r ) / 2 mid = (l+r)/2 mid=(l+r)/2
令 l = 0 l=0 l=0, r = n − 1 r=n-1 r=n−1
如果 m i d mid mid处所对的元素值小于 4 4 4，说明我们的端点 A A A一定不在 m i d mid mid点处，又因为这个序列是单调递增的，所以 m i d mid mid左侧的数字都是小于 m i d mid mid所对的值的。也就是说 m i d mid mid左侧的数字都是小于 4 4 4的，而我们的 A A A处是等于 4 4 4的。
那么知道这个有什么用呢？
这就说明 m i d mid mid的左侧包括 m i d mid mid都不可能是 A A A点，所以我们可以让 l = m i d + 1 l = mid + 1 l=mid+1。
如果 m i d mid mid处所对的值是大于等于 4 4 4的，说明 m i d mid mid右侧的值也一定是大于等于 4 4 4的。
而 m i d mid mid处的值也是等于 4 4 4的，也就是说 m i d mid mid处可能是答案，此时我们考虑一下 m i d mid mid右侧的情况。
如果 m i d mid mid右侧的值都比 m i d mid mid大，那么 m i d mid mid右侧的树也不可能是答案，因为他们都大于 4 4 4。
如果 m i d mid mid右侧还有等于 4 4 4的值，但这些不可能是答案，因为我们找的是区间的左端点，如果 m i d mid mid处是 4 4 4，那么 m i d mid mid右侧的 4 4 4肯定不是左端点。
通过上面对 m i d mid mid右侧的讨论，我们发现 m i d mid mid右侧都不可能是答案，但是 m i d mid mid处有可能是答案。所以我们可以扔掉 m i d mid mid右侧的数，即直接让 r = m i d r = mid r=mid。
通过一轮的比较，我们发现两端的端点再向中间靠拢。
因此我们只需要重复上面的比较，当左端点和右端点合并到一起的时候，那个点就是区间的左端点 A A A。
接着我们考虑区间的右端点。
右端点就是 B B B点，还是和刚才的思路一样，B点一定在这个数轴上，所以我们让左端点 l l l指向起点 0 0 0，右端点 r r r指向最后一个元素下标的 n − 1 n-1 n−1。
我们求出一个中点 m i d mid mid，
如果 m i d mid mid处所对的值是大于4的。
那么 m i d mid mid处肯定不符合条件，由于这个序列是单调递增的，所以 m i d mid mid右侧的数字也一定是大于4的，即不符合条件的。因此，我们可以直接扔掉 m i d mid mid所对的点和它右面的点。即 r = m i d − 1 r = mid - 1 r=mid−1
接着如果 m i d mid mid处所对的值是小于等于4的。
那么 m i d mid mid处有可能是答案，然后我们考虑 m i d mid mid左侧的值。
如果 m i d mid mid左侧的值都是小于4的，那么 m i d mid mid左侧的数字肯定不是答案，可以直接扔掉，如果 m i d mid mid左侧存在等于4的数，这些4也不可能是答案，因为我们找的是右端点，mid在这些4的右面。所以也可以扔掉。
因此如果 m i d mid mid处所对的值，我们可以直接扔掉 m i d mid mid左侧的数，但是需要保留 m i d mid mid，即 l = m i d l=mid l=mid
但是我们找左端点的时候， m i d = ( l + r ) / 2 mid=(l+r)/2 mid=(l+r)/2，而现在由于除法是下取整，所以mid的算法是 ( l + r + 1 ) / 2 (l+r+1)/2 (l+r+1)/2。
为什么呢？
我们看下面这个极端的例子：
2、模板
我们以下面的题目为例：
上述题目来自acwing网站
C++版
#include<iostream>using namespace std;const int N=1e6+10;int arr[N];int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++)scanf("%d",&arr[i]); while(m--) { //输入要查找的数字 int f=0; cin>>f; //开始二分： //寻找左边界 int l=0,r=n-1; int mid; while(l<r) { mid=(l+r)>>1; if(arr[mid]>=f)r=mid; else l=mid+1; } if(arr[l]!=f)cout<<"-1 -1"<<endl; else { cout<<l<<" "; //寻找右边界 l=0,r=n-1; while(l<r) { mid=(l+r+1)>>1; if(arr[mid]<=f)l=mid; else r=mid-1; } cout<<r<<endl; } } return 0;}二、浮点数二分
1、思路：
假设我们想求一个数字的立方根，并且要保留6位小数，那么必定存在一个范围都是满足这个答案的，因为通过四舍五入后，这个范围的答案都是正确的。此时我们就可以利用浮点数二分。
所以浮点数二分的思想就是，我们让l到r所组成的区间全部落在答案所在的范围内。此时我们在输出答案即可。
来自acwing。
2、代码：
C++版
#include<iostream>using namespace std;double x;double l=-10000.00;double r=10000.00;int main(){ cin>>x; while(r-l>1e-10) { double mid=(r+l)/2; if(mid*mid*mid>=x)r=mid; else l=mid; } printf("%.6lf",l);; return 0;}C
#include<stdio.h>double x;double l=-10000.00;double r=10000.00;int main(){ scanf("%lf",&x); while(r-l>1e-10) { double mid=(r+l)/2; if(mid*mid*mid>=x)r=mid; else l=mid; } printf("%.6lf",l);; return 0;}
