二分算法可以分为二分查找和二分答案。
以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。
首先明确二分查找与二分答案有何区别?
二分查找：在一个已知的有序数据集上进行二分地查找
二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案
二分查找
当我们要从一个序列中查找一个元素的时候，最快想到的方法就是暴力查找法（即：从前到后依次查找）。但这种方法过于无脑，适用于元素较少的时候，一旦元素个数多起来，效率是非常低下，所以在实际中这种查找的方法是被摒弃的。
这里就不得不介绍一种简单且效率较高的查找方法了：二分查找法，又称折半查找法。但该方法是建立在有序的前提下的。
二分查找法的前提条件是：查找的序列必须是有序的。即该序列中的所有元素都是按照升序或者降序排列好的，元素与元素只间的差值虽然是随机的，但始终是在递增或递减。
模板一（基本的二分查找）
这个场景是最简单的，肯能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1
int check(int num[],int size,int t){
int left=0,right=size-1; // 定义了t在左闭右闭的区间内，[left, right]
while(left<=right){ //当left==right时，区间[left, right]仍然有效
int mid=left+((right-left)/2);//等同于(left+right)/2，防止溢出
if(num[mid]>t){
right=mid-1; //t在左区间，所以答案在[left, mid-1]
}else if(num[mid]<t){
left=mid+1; //t在右区间，所以答案在[mid+1,right]
}else{ //num[mid]==t，找到答案
return mid;
}
}
return -1; //没有找到目标值
}声明一下，计算 mid 时需要防止溢出，代码中left+(right-left)/2就和(left+right)/2的结果相同，但是有效防止了left和right太大直接相加导致溢出
总结
因为我们初始化right=size-1
所以决定了我们的查找区间是[left, right]
所以决定了while (left<=right)
同时也决定了left=mid+1和right=mid-1
因为我们只需找到一个t的索引即可
所以当num[mid]==target时可以立即返回
模板二（寻找左侧边界的二分查找）
int check(int num[],int size,int t){
int left=0,right=size;
while(left<right){ //每次循环的查找区间是[left,right)左闭右开
int mid=(left+right)/2;
if(nums[mid]<t){
left=mid+1;
}else if(nums[mid]>t){
right=mid;
}else{ //两个条件可以合并为一个
right=mid;
}
}
return left; //终止的条件是left==right，此时搜索区间[left,left)为空，可以正确终止
}总结
因为我们初始化right=size
所以决定了我们的查找区间是[left, right)
所以决定了while (left < right)
同时也决定了left=mid+1和right=mid
因为我们需找到t的最左侧索引
所以当num[mid]==t时不要立即返回
而要收紧右侧边界以锁定左侧边界
模板三（寻找右侧边界的二分查找）
int check(int num[],int size,int t){
int left=0,right=size;
while(left<right){ //每次循环的查找区间是[left, right)
int mid=(left+right)/2;
if(num[mid]<t){
left=mid+1;
}else if(nums[mid]>target){
right=mid;
}else{ //两个条件可以合并为一个
left=mid+1;
}
}
return left-1; //终止的条件是left==right，此时搜索区间(right,right]为空，可以正确终止
}总结
因为我们初始化right=size
所以决定了我们的查找区间是[left, right)
所以决定了while (left < right)
同时也决定了left=mid+1和right=mid
因为我们需找到t的最右侧索引
所以当num[mid]==t时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须left=mid+1
所以最后无论返回left还是right，必须减一
对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的查找区间，我们还根据逻辑将查找区间全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：
int check(int num[],int size,int t){
int left=0,right=size-1;
while(left<=right){
int mid=left+(right-left)/2;
if(num[mid]<t){
left=mid+1;
}else if(num[mid]>t){
right=mid-1;
}else{
return mid;// 直接返回
}
}
return -1;
}
int check(int num[],int size,int t){
int left=0,right=size-1;
while(left<=right){
int mid=left+(right-left)/2;
if(num[mid]<t){
left=mid+1;
}else if(num[mid]>t) {
right=mid-1;
}else{
right=mid-1; //别返回，锁定左侧边界
}
}
if (left>=size||num[left]!=t){
return -1; // 最后要检查 left 越界的情况
}
return left;
}
int check(int num[],int size,int t){
int left=0,right=size-1;
while(left<=right){
int mid=left+(right-left)/2;
if(num[mid]<t) {
left=mid + 1;
}else if(num[mid]>t) {
right=mid-1;
}else{
left=mid+1;// 别返回，锁定右侧边界
}
}
if (right<0||num[right]!=t){
return -1;// 最后要检查 right 越界的情况
}
return right;
}如果以上内容你都能理解，那么恭喜你，二分查找也不过如此。。。
二分答案
什么是二分答案？
答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小。
判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间），一直往复，直至到最终的答案。
如何判断一个题是不是用二分答案做的呢?
典型特征:
求...最大值的最小 、 求...最小值的最大。
1.求...最大值的最小时，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让right=mid）
2.求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让left=mid）
1、答案在一个区间内（一般情况下，区间会很大，暴力超时）
2、直接搜索不好搜，但是容易判断一个答案可行不可行
3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
[NOIP2015 提高组] 跳石头 - 洛谷
我们二分的是最短距离，通过二分将这个最短距离（答案）最大化。那我们判断的时候肯定要保证mid是最短距离。
我们要求抽过石头剩下的石头中，两个石头间的最短距离为mid，那就要保证剩下的任意两个间距都要大于等于mid。要保证这个，那就只能挑间距大于等于mid的石头跳，中间的石头都将会被抽走。
最后，计数可以被抽走的石头。如果可以被抽走的石头个数小于等于需要抽的M个了，就说明满足条件。因为：既然抽了小于M个都能满足剩下的石头中，两石头间的距离都大于等于mid了，那抽M个，更能满足！
#include<cstdio>
using namespace std;
const int N=50005;
int d[N];
int main(){
int L,n,m,ans,x,left,right,mid;
scanf("%d%d%d",&L,&n,&m);
for(int i=0;i<n;i++){
scanf("%d",&d[i]);
}
left=0;right=L;
while(left<=right){
mid=(left+right)/2;
ans=0;
x=0;
d[n]=L;
for(int i=0;i<=n;i++){
if(d[i]-x<mid){
ans++; //两石头间距离小于mid，mid不是最短距离，不满足，移走该石头
}else{
x=d[i]; //符合，跳过去
}
}
if(ans<=m){
left=mid+1; //要的是距离的最大，所以尽可能地往右走
}else{
right=mid-1;
}
}
printf("%d",left-1);
return 0;
} Pie - HDU 1969
当你的中间取值都满足条件时，说明比它小的都满足条件，那么此时下界就变为中间取值，当中间取值不满足条件时，说明比它大的都不满足条件，那么这时候上界就变为中间取值。
由于题目输入给的是派的半径，因此我们需要转化为体积（高为1，面积就是体积）。
那么如何判断中间值是否满足条件呢？？？
求出每个派最多能分的人数（即派的面积除以中间值取整），再将人数相加，比较此时可分得总人数是否大于朋友数加自己（即F+1），若大于则中间值满足条件，更改下界值，反之亦然。
注意将PI放在输出时乘入可提高精度。PI=acos(-1)。
#include<cstdio>
#include<cmath>
using namespace std;
const double PI=acos(-1.0);
const int N=10005;
double a[N];
int main(){
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++){
int n,f,ans;
double left,right,mid,v;
scanf("%d%d",&n,&f);
f++;right=0;
for(int j=1;j<=n;j++){
scanf("%lf",&a[j]);
a[j]=PI*a[j]*a[j];
if(right<a[j]){
right=a[j];
}
}
left=0;
while(right-left>0.00001){ //注意精度要求，很重要！！！
mid=(left+right)/2;
ans=0;
for(int k=1;k<=n;k++){
ans+=(int)(a[k]/mid);
}
if(ans>=f){
left=mid;
}else{
right=mid;
}
}
printf("%.4lf\n",left);
}
return 0;
}二分中最痛苦的问题就是边界问题。。。。。
至于边界问题，请待下回分解！！！
文章来源：https://www.toymoban.com/news/detail-472446.html
文章来源地址https://www.toymoban.com/news/detail-472446.html
到了这里，关于C++二分算法(二分查找&二分答案)细节详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
