题解34 【模板】整数域二分

前言：又是一道模板题，我感觉关于边界的问题不好考虑，确定好自己唯一的一种写法就好。我的写法是按照正常思路考虑，然后求<=的最后一个元素时将mid=l+(r-l+1)/2，即(l+r+1)/2，写成r-l可以将让两个int范围边缘的正数相加不超限。后附有二分代码与使用STL函数的代码

AC代码（学习二分思想）：

#include<iostream>
#include<algorithm>
using namespace std;
int a[200010];
int n;
int solve1(int x)//找>=x第一个位置的下标
{
    int mid;
    int l=1,r=n;
    while(l<r)
    {
        mid=l+(r-l)/2;
        if(a[mid]>=x) {r=mid;}//要求第一个元素，下标肯定越小越好，将右边界调为mid(此时>=x)，就算mid刚好是>=x的第一个元素也没有关系，l会一直=mid+1，直到l==r
        else {l=mid+1;}//如果mid<x，由于a已经递增排序过了，让l不断右移，直到出现a[mid]>=x，划到上面if中那种情况
    }
    return r;
}
int solve2(int x)//找<=x最后一个位置的下标
{
    int mid;
    int l=1,r=n;
    while(l<r)
    {
        mid=l+(r-l+1)/2;//经验，记住算了...
        if(a[mid]<=x) {l=mid;}//要求最后一个元素，下标肯定越大越好，左边界调为mid（<=x），就算mid刚好是<=x最后一个位置也没关系，r会一直-1，直到来到l身旁，最终l==r退出循环
        else {r=mid-1;}//mid>x说明mid太大了,让r不断左移，直到出现a[mid]<=x，划到上面if中那种情况
    }
    return r;
}
int main()
{    
    ios::sync_with_stdio(0);cin.tie(0);
    int q;
    cin>>n>>q;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    sort(a+1, a+1+n);//排序后才二分
    int t1,t2;
    while(q--)
    {
        cin>>t1>>t2;
        cout<<solve2(t2)-solve1(t1)+1<<'\n';//别忘了加1哦，植树原理，区间下标之差再＋1
    }
    return 0;
}

AC代码（使用STL函数）:

#include<iostream>
#include<algorithm>
using namespace std;
int a[200010];
int n;
int main()
{    
    ios::sync_with_stdio(0);cin.tie(0);
    int q;
    cin>>n>>q;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    sort(a+1, a+1+n);//注意upper_bound与lower_bound必须对排过序的数组操作，不然是未定义行为
    int t1,t2;
    while(q--)
    {
        cin>>t1>>t2;
        cout<<upper_bound(a+1, a+1+n, t2)-lower_bound(a+1, a+1+n, t1)<<'\n';//lower_band返回的是第一个不小于>=x的元素，但！upper_band返回的是第一个>x的元素迭代器（高级版指针），也就是<=x最后一个位置的下标+1,相当于上面那种AC代码中已经加过1，不用再＋1了
    }
    return 0;
}