从一个有序数组中查找某个值

这是二分法最常用到的地方，也即折半查找法，在C++的STL库中有相关的lower_bound和upper_bound函数进行实现。

下面用代码块来实现STL中的lower_bound:

int n,k;//n为数组的大小，数组为a[0~n-1]，k为要搜索的值
int a[MAX_N];

int Lower_bound()//找到满足ai>=k的最小的k值
{
    int lb=-1,ub=n;//初始化解的范围(lb,ub)
    
    while(ub-lb>1)//重复循环直到解的存在范围不大于一
    {
        int mid=(lb+ub)/2;
        
        if(a[mid]>=k)//如果mid满足条件，则解的范围变成(lb,mid]
        {
            ub=mid;
        }
        else //如果不满足，则解的范围变为(mid,ub]
        {
            lb=mid;
        }
    }
    
    //此时lb+1=ub,区间为(lb,ub],则ub为所求
    return ub;
}

该lower_bound算法也可拓展为求解满足某一个条件的最小值算法

=>推广：有N条绳子，长度为\(L_i\)，从中切出长度相等的K段，求每段最长为多少。

int N,K;
double L[MAX_N];//输入

bool fit(double x)//判断该分割是否满足条件
{
    int num=0;
    for(int i=0;i<N;i++)
    {
        num=num+(int)(L[i]/x);
    }
    return num>=x;
}

double solve()
{
    double lb=0,ub=INF;//初始化解的范围(lb,ub)
    
    for(int i=0;i<100;i++)//此时相当于有ub-lb<1e-30
    {
        double mid=(lb+ub)/2;
        if(fit(mid)) lb=mid;//解的范围[mid,ub)
        else ub=mid;//解的范围(lb,mid]
    }
    return ub;//近似看作lb==ub
}

最大化最小值

将M个物品放在一条直线的N个位置，求使两两之间距离的最小值最大的值：

int N,M;
int x[MAX_N];//输入

bool fit(int d)//判断此时的d是否满足条件
{
    int last=0;
    for(int i=1;i<M;i++)
    {
        int crt=last+1;
        while(crt<N && x[crt]-x[last]<d)
        {
            crt++;
        }
        if(crt==N)return false;
        last=crt;
    }
    return true;
}

int solve()
{
    sort(x,x+N);//先对x数组排序
    
    int lb=0,ub=INF;//初始化解的范围(lb,ub);
    
   while(ub-lb>1)
   {
       int mid=(lb+ub)/2;
       if(fit(mid))lb=mid;//缩小为[mid,ub)
       else ub=mid;//缩小为[lb,mid)
   }
   return lb;
}