二分

情况导入

如果在生活中，有一个人，让你猜在 \(1\) 到 \(100\) 之间的一个数，你该怎么猜？

假设答案是 \(20\)，那我们应该这样猜：

先猜 \(50\)，大了。

随后猜 \(25\)，还是大了。

再猜 \(15\)，小了。

最后猜 \(20\)，对了。

我们其实可以发现，能最快猜到的办法肯定是在一个区间中取中间数查找。

那我们在编程中也可以如此，例如在数组 \(a\) 中查找一个数，那我们也应该这么找（这样的前提是必须具有单调性的），在很多个下标中选取中间的那个来搜。大了，就往左边搜，小了，就往右边搜。

Code

代码也很简单，就跟刚刚说的相似：

//核心代码
while(l<=r){
    int m=(l+r)>>1;
    if(a[m]>=x)p=m,r=m-1;
    else l=m+1;
}

题目实战

洛谷P2249

题目大意：

现在有 \(n\) 个数，有 \(m\) 个查询，问你在这 \(n\) 个数中，出现的下标是多少？

思路

可以直接套用二分模板，找到后输出就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn=1e6+10;
int a[maxn];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    for(int i=0;i<m;++i){
        int x;
        cin >> x;
        int l=1,r=n,p=n+1;
        while(l<=r){
            int m=(l+r)>>1;
            if(a[m]>=x)p=m,r=m-1;
            else l=m+1;
        }
        if(p<=n && a[p]==x)cout << p << " ";
        else cout << -1 << " ";
    }
    return 0;
}

洛谷 P1102

题目大意

给你一串数 \(a\)，和一个数字 \(c\)，使得 \(a\) 数组中的两个数相减等于 \(c\)。

思路

同理，我们枚举 \(a_i\)，再二分 \(a_i-c\)即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,c,a[maxn];
long long ans;
int find(int x){
    int l=1,r=n,p=n+1;
    while(l<=r){
        int m=(l+r)>>1;
        if(a[m]>=x)p=m,r=m-1;
        else l=m+1;
    }
    if(p<=n && a[p]>=x)return p;
    else return 0;
}
int main(){
    cin >> n >> c;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i){
        int k=a[i]-c;
        int p=find(k),q=find(k+1);
        ans+=(q-p);
    }
    cout << ans << endl;
    return 0;
}

总结

想二分这种题，我们要多多练习，理解每一行的意思。

感谢观看。