二分二分查找模板

1.查找元素k的位置

输入

3
123 132 145
1
123

输出

1

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n;
ll find1(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]==k)
            return mid;
        else if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
    }
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    ll m;
    scanf("%lld",&m);
    ll k;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld",&k);
        printf("%lld\n",find1(k));
    }
}

2.查找第一个大于等于k的元素位置

输入

6
1 2 2 3 3 4
4
1 2 3 4

输出

1
2
4
6

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n;
ll find1(ll k)
{
    ll l=1,r=n+1; //搜索时左闭右开,while循环l<r即可
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
        else if(a[mid]==k)
            r=mid;
    }
    return l;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    ll m;
    scanf("%lld",&m);
    ll k;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld",&k);
        printf("%lld\n",find1(k));
    }
}

2.查找最后一个小于等于k的元素位置

输入

6
1 2 2 3 3 4
4
1 2 3 4

输出

1
3
5
6

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n;
ll find1(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
        else if(a[mid]==k)
            l=mid+1;
    }
    return l-1; // 由于l=mid+1 所以l不是答案
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    ll m;
    scanf("%lld",&m);
    ll k;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld",&k);
        printf("%lld\n",find1(k));
    }
}

用二分法解题时，mid上下取值正确与否关系程序是否进入死循环！！

对与if(test(mid)) l=mid; else r=mid-1; 如果用 mid=(l+r)/2 会出现问题！！！ 取l=3,r=4,会发现程序死循环！！！得用 mid=l+(r-l+1)/2;

对于if(test(mid)) r=mid; else l=mid+1; 显然得用mid=(l+r)/2

两种方式一个向上，一个向下取整，具体问题具体分析！！

参考于：

https://blog.csdn.net/wakouboy/article/details/22995997

https://www.jianshu.com/p/f3e3a84d7b8c

https://www.cnblogs.com/luoxn28/p/5767571.html

----------------------------------分割线-----------------------------------------------------

http://icpc.upc.edu.cn/problem.php?cid=1405&pid=9

题目描述

有一天，贪吃的猪八戒来到了一个大果园，果园里有n(n≤100000)个大西瓜，每个西瓜 的质量不大于长整型(longint)，并且每个西瓜的质量都不同。猪八戒非常无聊，先把所有的西瓜按从小到大排列，然后再选m(m≤l00000)个质量是Ki的西瓜，请你帮他把想吃的西瓜找出来。

输入

第1行输入n，然后以下n行输入n个整数； 接着输入m，然后以下m行，每行一个整数Ki。

输出

输出m行，每行一个整数，表示重新排列后，Ki在这N个数中的位置。

样例输入

3
132
123
145
1
123

样例输出

1

简单的排序+二分查找

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n;
ll find1(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]==k)
            return mid;
        else if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
    }
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll m;
    scanf("%lld",&m);
    ll k;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld",&k);
        printf("%lld\n",find1(k));
    }
}

http://icpc.upc.edu.cn/problem.php?cid=1405&pid=11

题目描述

我有很多（n条）珍珠项链，每天我都要从中挑一条戴上……挑哪条很有讲究，不能太难看也不能太好看。所以我希望你能帮帮我，解决这个问题――每天帮我算算，那天我能戴的项链有多少条。

输入

第1行为正整数n，表示项链的总条数(n≤100000)； 第2行有n个整数（代表每条项链晶的好看程度Xi，0≤Xi≤maxlongint）； 第3行为正整数m，表示总天数(也就是总询问次数，其中m≤100000)； 以下m行，每行两个整数Ai，Bi(1≤Ai，Bi≤maxlongint)，询问好看程度在Ai到Bi之间的项链条数（含等于Ai或Bi的，Ai与Bi大小关系不确定）。

输出

输出m行，对于每次询问输出一行，从Ai到Bi(含Ai，Bi)好看程度在Ai到Bi之间的项链条数。

样例输入

7
8 2 3 5 6 7 7
6
1 5
8 6
1 10
5 5
4 4
7 8

样例输出

3
4
7
1
0
3

查找左右边界做差即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n;
ll find1(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
        else if(a[mid]==k)
            l=mid+1;
    }
    return l-1;
}
ll find2(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
        else if(a[mid]==k)
            r=mid;
    }
    return l;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll m;
    scanf("%lld",&m);
    ll o,p;
    for(ll i=1; i<=m; i++)
    {
        scanf("%lld%lld",&o,&p);
        if(o>p)
            swap(o,p);
        printf("%lld\n",-find2(o)+find1(p)+1);
    }
}

http://icpc.upc.edu.cn/problem.php?cid=1405&pid=10

题目描述

万圣节又到了！FJ打算带他的奶牛去参加化装晚会，但是，FJ只做了一套能容下两头总长不超过S (1≤S≤1000000)的奶牛恐怖服装。FJ养了N(2≤N≤20000)头按1--N顺序编号的奶牛，编号为i的奶牛的长度为L_i(1≤L_i≤1000000)。如果两头奶牛的总长度不超过S，那么她们就能穿下这套服装。 FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。

输入

第1行是2个整数：N和S； 第2～N+l行每行一个整数：L_i。

输出

1个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种方案是被视为相同的。

样例输入

4 6
3
5
2
1

样例输出

4

提示

样例说明：4种选择分别为：奶牛1和奶牛3；奶牛l和奶牛4；奶牛2和奶牛4；奶牛3和奶牛4。 二分，查找符合条件的上界求和即可。

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500]= {0};
ll n,k;
ll find1(ll k)
{
    ll l=1,r=n+1;
    while(l<r)
    {
        ll mid=(l+r)/2;
        if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
        else if(a[mid]==k)
            l=mid+1;
    }
    return l-1;
}
int main()
{
    scanf("%lld%lld",&n,&k);
    for(ll i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    ll sum=0;
    for(ll i=1;i<=n;i++)
    {
        ll w=find1(k-a[i]);
        if(i<=w)
            w--;
        sum+=w;
    }
    cout<<sum/2<<endl;
}

附上一份二分查找的模板

#include <bits/stdc++.h>

using namespace std;
int a[100500]= {0};  ///从小到大排序
int n,m;
int find1(int k)     ///查找某一个数第一次出现的位置
{
    int l=1,r=n,mid;
    while(l<r)       ///while循环条件为l<r,则跳出循环时l==r,减少对返回值的考虑
    {
        mid=(l+r)/2; ///由于是l=mid+1,建议用(l+r)/2
        if(a[mid]==k)
            r=mid;
        else if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
    }
    if(a[r]==k)
        return r;
    else
        return -1;
}
int find2(int k)     ///查找某一个数最后一次出现的位置
{
    int l=1,r=n,mid;
    while(l<r)
    {
        mid=(l+r+1)/2; ///由于是r=mid-1,建议用(l+r+1)/2
        if(a[mid]==k)
            l=mid;
        else if(a[mid]>k)
            r=mid-1;
        else if(a[mid]<k)
            l=mid;
    }
    if(a[l]==k)
        return l;
    else
        return -1;
}
int find3(int k)     ///查找第一个大于等于k的元素位置
{
    int l=1,r=n,mid;
    while(l<r)
    {
        mid=(l+r)/2; ///由于是l=mid+1,建议用(l+r)/2
        if(a[mid]==k)
            r=mid;
        else if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
    }
    if(a[l]>=k)
        return l;
    else
        return -1;
}
int find4(int k)     ///查找第一个大于k的元素位置
{
    int l=1,r=n,mid;
    while(l<r)
    {
        mid=(l+r)/2; ///由于是l=mid+1,建议用(l+r)/2
        if(a[mid]==k)
            l=mid+1;
        else if(a[mid]>k)
            r=mid;
        else if(a[mid]<k)
            l=mid+1;
    }
    if(a[l]>k)
        return l;
    else
        return -1;
}
int find5(int k)       ///查找最后一个小于等于k的元素位置
{
    int l=1,r=n,mid;
    while(l<r)
    {
        mid=(l+r+1)/2; ///由于是r=mid-1,建议用(l+r+1)/2
        if(a[mid]==k)
            l=mid;
        else if(a[mid]>k)
            r=mid-1;
        else if(a[mid]<k)
            l=mid;
    }
    if(a[l]<=k)
        return l;
    else
        return -1;
}
int find6(int k)       ///查找最后一个小于k的元素位置
{
    int l=1,r=n,mid;
    while(l<r)
    {
        mid=(l+r+1)/2; ///由于是r=mid-1,建议用(l+r+1)/2
        if(a[mid]==k)
            r=mid-1;
        else if(a[mid]>k)
            r=mid-1;
        else if(a[mid]<k)
            l=mid;
    }
    if(a[l]<k)
        return l;
    else
        return -1;
}
int main()
{
    printf("请输入数字个数:\n");
    scanf("%d",&n);
    printf("请输入一行数字,不必分前后顺序:\n");
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    printf("请输入要查询的数字:\n");
    while(scanf("%d",&m)!=EOF)
    {
        int ans1,ans2,ans3,ans4,ans5,ans6;
        ans1=find1(m);
        ans2=find2(m);
        ans3=find3(m);
        ans4=find4(m);
        ans5=find5(m);
        ans6=find6(m);
        printf("%d 第一次出现的位置为 %d\n",m,ans1);
        printf("%d 最后一次出现的位置为 %d\n",m,ans2);
        printf("第一个大于等于数字 %d 的位置为 %d\n",m,ans3);
        printf("第一个大于数字 %d 的位置为 %d\n",m,ans4);
        printf("最后一个小于等于数字 %d 的位置为 %d\n",m,ans5);
        printf("最后一个小于数字 %d 的位置为 %d\n",m,ans6);
        printf("请输入要查询的数字:\n");
    }
}