二分

找最大

bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;//check中的mid符合条件包含
        else r = mid - 1;
    }
    return l;
}
//有可能不存在，需要特判一下是否存在.

找最小

bool check(int x) {/* ... */} // 检查x是否满足某种性质

int bsearch(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;//check中的mid符合条件包含
        else l = mid + 1;
    }
    return l;
}
//有可能不存在，需要特判一下是否存在.

1.杨辉三角

在杨辉三角中给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数。

杨辉三角除了几何模型上的数关系外，每一行都是排列组合的结果，通过这个来查找某一行某一列的数的大小，由于题目数据比较大，则采用二分查找降低时间复杂度

# include <stdio.h>
# include <string.h>
# include <algorithm>
# include <iostream>
# include <functional>
using namespace std;
#define LL long long
const int maxn=1e8;

LL int node(LL int q,LL int p)//输出第q行第p列的值的大小
{
    LL int sum=1;
    for(int i=q;i>=q-p+1;--i)
    {
      sum*=i;
    }
    for(int j=1;j<=p;++j)
    sum/=j;
    return sum;
}

LL int jie(int k)//算出前面有几个数（也可以用等差数列公式）
{
    LL int zong=0;
    for(int i=1;i<=k;++i)
    zong+=i;
    return zong;
}
int main()

{
    int n;
    cin>>n;
    int sum=0;
    if(n==1)
    cout<<1<<endl;//特殊情况
    else{
        for(int i=20;i>=0;--i)//对每一列进行查找
        {
            int l=2*i;
            int r=n;
            while(l<=r)//二分查找
            {
                int mid=(l+r)>>1;
                LL int o=node(mid,i);
                if(o==n)
                {
                    sum=1;
                    cout<<jie(mid)+i+1<<endl;
                    break;
                }
                else if(o>n)//大了的话行数变小
                {
                    r=mid-1;
                }
                else//行数变大
                l=mid+1;
            }
            if(sum==1)
            break;
        }
    }
}

2.wyh的物品

wyh学长现在手里有 nnn 个物品，这 nnn 个物品的重量和价值都告诉你，然后现在让你从中选取 kkk 个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的 kkk 个物品的总价值和总重量的比值）.

本题不能采用dp，算出每一个物品的单位价值的和不等于总价值和总质量的比值；由于我们要查找最大单位价值，则可以采用二分去找出最大的单位价值

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=1e5+5;

int n,k;
ll w[maxn],v[maxn];
double c[maxn];

bool check(double x)//判断
{
    for(int i=1;i<=n;++i)
        c[i]=v[i]-x*w[i];
    sort(c+1,c+n+1);//对最后剩余的价值进行排序（升序）
    double res=0;
    for(int i=n;i>n-k;--i)//取大的
        res+=c[i];
    return res>=0;//如果最后的价值仍有剩余，则mid可以更大，选择右区间
}

int main()
{
    //cin.tie(0)->sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;++i)
            scanf("%lld %lld",&w[i],&v[i]);
        double l=0,r=1e9;
        while(r-l>1e-5)//二分
        {
            double mid=(r+l)/2;
            if(check(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.2lf\n",r);
    }
}