二分专题
y总的二分模板

//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; 
        else l = mid + 1; 
    }   
    return l;
}
//查找右边界 SearchRight 简写SR 
int SR(int l, int r) 
{
    while (l < r)
    {                   
        int mid = l + r + 1 >> 1; //需要+1 防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1; 
    }
    return r; 
}

第一题： 数的范围

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,q,k;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--)
    {
        int k;
        cin>>k;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(a[mid]>=k) r=mid;
            else l=mid+1;
        }
        if(a[l]!=k)
        {
            cout<<-1<<" "<<-1<<endl;
            continue;
        }
        int l2=1,r2=n;
        while(l2<r2)
        {
            int mid=(l2+r2+1)>>1;
            if(a[mid]<=k) l2=mid;
            else r2=mid-1;
        }
        cout<<l-1<<" "<<l2-1<<endl;
    }
    return 0;
}

第二题： 二分查找应用5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,q;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(a[mid]<=x) l=mid;
            else r=mid-1;
        }
        if(a[l]==x) cout<<l<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

第三题： 二分查找应用6

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,q;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(a[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(a[r]==x) cout<<r<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}

第四题： 化妆晚会
思路：先从小到大排序，从后枚举，若当前元素<s,二分查找<=s-a[i]的下标最大元素位置L，则此坐标以及之前的元素都可配对，则答案+L。注意配对的两位置不能为同一元素，题目要求两个牛。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,s;
ll ans=0;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--)
    {
        if(a[i]>=s) continue;
        else
        {
            int l=1,r=i-1;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(a[mid]<=s-a[i]) l=mid;
                else r=mid-1;
            }
            if(a[l]<=s-a[i])
            {
                if(l!=i) ans+=l;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

第五题： 区间询问
这一题解题思路很简单，就是二分查找，但是这题时间复杂度卡的很死，用scanf和printf或关流。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
ll n,q;
ll a[100010];
int main()
{
    scanf("%lld %lld",&n,&q);
    for(ll i=1;i<=n;i++) cin>>a[i];
    while(q--)
    {
        ll l,r,x;
        scanf("%lld %lld %lld",&l,&r,&x);
        ll l1=l,r1=r;
        while(l1<r1)
        {
            ll mid=(l1+r1+1)>>1;
            if(a[mid]<x) l1=mid;
            else r1=mid-1;
        }
        if(a[l1]<x) printf("%lld\n",l1-l+1);
        else printf("%lld\n",0);
    }
    return 0;
}

第六题： 桐桐查单词
思路：本题重点在于使用结构体存储数据和如何对结构体数组进行排序，以及字符串如何比大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
struct str
{
    string s;
    int num;
} a[20010];
bool cmp(struct str a,struct str b)
{
    return a.s<b.s;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].s;
        cin>>a[i].num;
    }
    sort(a+1,a+n+1,cmp);
    cin>>m;
    while(m--)
    {
        string ss;
        cin>>ss;
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(a[mid].s<=ss) l=mid;
            else r=mid-1;
        }
        if(a[l].s==ss) cout<<a[l].num<<endl;
    }
    return 0;
}

第七题： 解方程
思路：这题通过二分逼近答案，当误差在允许范围内时就输出答案，题目y的范围为：[-1000000000,1000000000]，通过观察函数: f(x) = 2x^5+7x^3+100 ，发现x^5应该是主体，1000000000开5次方约为64多一点。所有二分的左右端点可以设置小一点，我设了l=-100,r=100。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
double y;
double f(long double x)
{
    return 2*pow(x,5)+7*pow(x,3)+100;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>y;
    double l=-100,r=100;
    while(l<r)
    {
        double mid=(l+r)/2;
        double cnt=f(mid);
        if(cnt<y) l=mid;
        else r=mid;
        if(abs(cnt-y)<=0.001)
        {
            cout<<mid<<endl;
            break;
        }
    }
    return 0;
}

第八题： 得分
思路：设第一第二个人的能力值分别为a,b(a>=b),由题目得：(a+b)*(a-b)==m,化简一下为 a^2-b^2==m。所以先按从小到大排序，从后开始遍历，每次二分寻找值为 a^2-m 的元素的左右端点l,r,答案+=r-l+1。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,m;
int a[100010];
ll ans;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=n;i>=1;i--)
    {
        int t=a[i]*a[i]-m;
        int l=1,r=i-1;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(a[mid]*a[mid]<=t) l=mid;
            else r=mid-1;
        }
        if(a[l]*a[l]!=t) continue;
        int l1=1,r1=i-1;
        while(l1<r1)
        {
            int mid=(l1+r1)>>1;
            if(a[mid]*a[mid]>=t) r1=mid;
            else l1=mid+1;
        }
        ans+=l-l1+1;
    }
    cout<<ans<<endl;
    return 0;
}

第九题： 分苹果
思路：二分最小箱子重量，二分左端点为最大苹果重量，右端点要设置的大一点为10000，每次二分判断将所有苹果装完所需的箱子数量，若是<=k,表示此时箱子容纳重量过大，更新r=mid,否则更新l=mid+1。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
ll n;
ll a[100010];
ll k;
ll solve(ll mid)
{
    ll ans1=0;
    ll t=mid;
    for(ll i=1;i<=n;i++)
    {
        if(a[i]<=t)
        {
            if(t==mid) ans1++;
            t-=a[i];
        }
        else
        {
            t=mid;
            if(a[i]<=t)
            {
                if(t==mid) ans1++;
                t-=a[i];
            }
        }
    }
    return ans1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    ll maxs=-1;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
        maxs=max(maxs,a[i]);
    }
    ll l=maxs,r=1000;
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(solve(mid)<=k) r=mid;
        else l=mid+1; 
    }
    cout<<l<<" "<<endl;
    return 0;
}

第十题： 木材加工

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e6+5;
int n,k;
int a[100010];
int solve(int x)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=a[i]/x;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    int maxs=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        maxs=max(maxs,a[i]);
    }
    int l=1,r=1e9;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(solve(mid)>=k) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}