一 . 二分法

二分搜索又叫做二分查找、折半查找，它是一种效率较高得查找方法。

二分搜索得要求：

线性表为有序表，并且要用向量作为表得存储结构。

二分搜索得基本思想：先确定待查找记录所在的范围，然后逐步缩小范围直至找到或找不到该记录位置。

二分查找步骤：

1、先确定中间位置：

middle = (left+right)/2;

2、将待查找得key值与data[middle].key值相比较。若相等，则查找成功并返回该位置，否则须确定新得查找区间，继续二分查找，具体方法如下：

如果data[middle].key大于key，由于data为有序线性表，可知data[middle...right].key均大于key，因此若表中存在关键字等于key得节点，则一定在位置middle左边的子表中。

反之，　data[middle].key小于key，　因此若表中存在关键字等于key得节点，则一定在位置middle右边的子表中。下一次查找针对新得区域进行查找。

二分答案：

简单地讲一下二分答案，和为什么什么时候用二分答案。当一道题目直接求解答案会很困难，但是根据题意去验证答案会很简单，那么我们就利用逆向思维，直接枚举答案，利用刚刚学到的二分查找去查找答案，然后去直接按照题意验证答案，验证成功即可输出，所以二分更多的就是逆向思维
例如下面这道题目

1.

二分法是一种快速寻找元素的方法，但又不是一种单纯的快速寻找的方法，其寻找的元素是需要一个单调有序的元素，所以在题目中如果遇到了需要排序然后寻找的，我们可以首要考虑二分法，前提是对于世界没有要求，二分法可以很迅速的找到我们所找到的元素。

二分法的实现方式是：

先将一串元素分为左右两部分，然后用中间值与所需值比较，若中间值较小，那么便取中间值与右边的边界的中间值，继续与所需值比较。若中间值较大，那么便取左边的边界与中间值的中间值，再与所需值比较，然后重复此过程，最终找到我们所需要的结果，这是一种思想，也是一种应用。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
double a,d,e;
int b,k,t;
const double f=1e-4;
double c[100000];
int min(int a,int b)
{
	if(a<b)return a;
	else return b;
}
int max(int a,int b)
{
	if(a>b)return a;
	else return b;
}
void hs(double d,double e)
{
    double mid;
    while(d+f<e)
    {
        mid=(d+e)/2.0;
        int g=0;
        for(int h=1;h<=a;++h)
        {
            g+=c[h]/mid;
        }
        if(g>=k)d=mid;
        else e=mid;
    }

    printf("%f\n",e);
}
int main()
{
cin>>t;
while(t--)
{
    cin>>a>>k;
    for(b=1;b<=a;++b)
    {
       cin>>c[b];
       d=min(d,c[b]);
       e=max(e,c[b]);
    }
      hs(d,e);
}
    return 0;
}

2.

使用二分法操作，
圆台上下底面大小看题意，并不是非要上底半径大于下底这个需要按上次讲的二分思想来做

    普通：     
    ******************************************************     
 


   while (l <= r)     
    {         
        mid = (l + r) / 2;         
    if (check(mid))              
        l = mid + 1;            
    else              
        r = mid - 1;      
    }     

    浮点数：     
    ******************************************************     

const double EPS = 1e-9;//精确数 
double l = 0, r = 100 * 1.0, mid;    
 while (r - l >= EPS) 
{        
    mid = (l + r) / 2;  
         
    if (judge(mid))             
        l = mid + EPS;         
    else              
        r = mid - EPS;   
}     

     ****************************************************** 

#include<bits/stdc++.h>
using namespace std;
const double EPS=1e-9;
const double pi=acos(-1.0);//得到π的值
double r1,r2,h,v;
bool check (double x)
{
    double R=1.0*r1+(r2-r1)*x/h;
    return 1.0/3*pi*x*(r1*r1+R*R+r1*R)<v;
}
int main()
{
    while(cin>>r1>>r2>>h>>v)
    {
        double V=1.0/3*pi*h*(r1*r1+r2*r2+r1*r2);
        if(v>=V)
        {
            printf("%.3lf\n",h);
            continue;
        }
        double l=0,r=100*1.0,mid;
        while(r-l>EPS)
        {
            mid=(l+r)/2.0;
            if(check(mid))
                l=mid+EPS;
            else r=mid-EPS;
        }
        printf("%.3lf\n",(l+r)/2.0);
    }
    return 0;
}

玄学的二分（二分答案）

二分本身并不玄学，因为用的人比较***（我），所以就需要玄学调参

其实总体来说，分不同的题目，二分的参数就必须准确，这一点小细节极为重要。

比如浮点数的二分物品，需要：while(l+EPS<r)
整数的二分有时候可能没办法使得l>r，就需要写成while(l+1<r)

比如下面的题目：
P1873 砍树

~~我写这种题都要WA一次真是丢脸~~

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大

const ll N=1000007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-6;
#undef mid

ll n,m,arr[N];
ll r;

inline bool check(ll k)
{
    ll sum=0;
    over(i,1,n)
    sum+=arr[i]>k?(arr[i]-k):0;
    return sum>=m;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    over(i,1,n)scanf("%lld",&arr[i]),r=max(r,arr[i]);
    ll l=0,mid;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%lld",l);
    return 0;

}