二分算法--模板及原理总结

二分答案

首先我们看这个图：

我们需要二分的答案就是这个临界点x。

什么情况下可以使用二分呢：
具有单调性（单调递增，单调递减），二段性（整个区间一分为二，一段区间满足，一段区间不满足），那个点x就是我们需要二分寻找的点。

二分的模板：
1. 图中第一种情况：
mid=（l+r）/ 2；，if ( check（mid ) ）r=mid，l=mid+1；
2.图中第二种情况：
mid=（l+r+1) / 2， if ( check（mid ) ）l=mid，r=mid-1；

//写check ，满足与不满足分别更新哪个区间；
// 二分一定可以二分出满足性质的数，但是结果需要判断是否符合性质；


例题：点击跳转例题

代码：

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'
#define LL __int128

using namespace std;

const int N=2e5+10,M=1e3+10,mod=998244353,INF=0x3f3f3f3f;

int a[N],b[N],c[N],pre[N];

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n,q;cin>>n>>q;
    for(int  i=0;i<n;i++)
        cin>>a[i];

    while(q--)
    {
        int x;cin>>x;
        //注意r不能开大了，不然会超出数组的值，这样check数组外的值为0就会出错
        int l=0,r=n-1;
        while(l<r)
        {
            //二段性：这个点后面的部分都满足
            //用图一第一套模板
            int mid=(l+r)/2;
            if(a[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(a[l]!=x)
            cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<' ';
            int l=1,r=n-1;
            while (l<r)
            {
                //二段性：这个点前面的部分都满足
                //用图一第二套模板
                int mid=(l+r+1)/2;
                if(a[mid]<=x)l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}