本文介绍了如何利用二分查找算法解决两个经典的编程问题。第一个问题是“牛可乐和魔法封印”，需要统计一个有序数组中落在给定区间内的元素个数，通过两次二分查找分别定位区间的起始和结束位置来实现。第二个问题是“A-B数对”，要求找出数组中满足a[i] - a[j] = c的数对个数，通过将问题转化为在排序数组中查找特定差值，并借助STL中的upper_bound和lower_bound函数高效求解。两种方法都展示了二分查找在优化算法效率方面的强大作用。

⭐ 在“牛可乐和魔法封印”问题中，核心是通过二分查找来统计一个有序数组中位于给定区间[x, y]内的元素数量。具体实现是先找到第一个大于等于x的元素的位置，再找到第一个大于y的元素的位置，两者之差即为符合条件的元素个数，需要注意边界条件的细微处理。

✨ 对于“A-B数对”问题，将其转化为在数组中查找满足a[i] - a[j] = c的数对，等价于寻找a[i] - c = a[j]。在对数组排序后，对于每个元素a[i]，只需在a[1]到a[i-1]的范围内查找等于a[i]-c的元素个数。

📊 使用C++ STL中的`upper_bound`和`lower_bound`函数可以高效地实现上述查找。`lower_bound(begin, end, value)`返回第一个不小于value的元素的迭代器，而`upper_bound(begin, end, value)`返回第一个大于value的元素的迭代器。两者的差值即为value在指定范围内出现的次数。

💻 两个问题都依赖于数据预先排序，这使得二分查找成为可能。排序操作的时间复杂度通常为O(N log N)，而每次二分查找的时间复杂度为O(log N)。对于“牛可乐和魔法封印”，总时间复杂度为O(N log N + Q log N)，其中Q是查询次数。对于“A-B数对”，总时间复杂度为O(N log N + N log N)，即O(N log N)。

1.牛可乐和魔法封印

下面的这个算是我自己学习这个二分算法的第一道正式的题目：关于这个非常奇怪的题目，但是看看这个测试用例就知道这个题目需要我们做的这个事情了；

输入的5表示我们输入的数据的个数，3表示的就是我们需要查找的数据范围的要求，比如这个2-6之间，在我们输入的5个数据里面，就是2345这四个符合要求的数据；

1-5这个区间，显然输入的这五个数据都是没有问题的，3-3这个区间，显然只有一个数据符合要求，然后把这个符合要求的数据的个数直接输出即可

下面的这个是我们的代码：

1）先看一下主函数里面的输入的内容，循环输入n个数据，q表示的就是我们的查询的次数，其中每一次进行查询的时候都需要进行两个元素的输入即可，在这个输入的过程之哦吼调用我们封装的这个自定义函数，用来计算这个数组里面的符合数据范围的要求的数据的个数即可；

2）在我们的这个自定义函数里面，其实还是一样的道理，就是找到这个大于等于x第一次出现的位置，使用二分的思想；

然后找到这个第一次符合元素的位置，如果结束之后这个指针的指向还是小于x的，证明这个数据里面就没有符合要求的这个元素，我们直接返回0即可；

第二个循环里面查找的就是符合要求的元素里面的最后一个位置，这个时候我们也是进行这个区间的划分，把这个区间划分成为小于等于y和大于y的两个部分，当这个过程结束的时候，我们直接判断一下这个时候left指向的位置是不是符合要求的，如果是大于y的，证明我们的这个数组里面的元素都是大于y的，也就是说我们的这个数组里面是没有符合要求的这个元素的，这个时候我们直接返回这个0即可；

3）最后需要我们返回这个符合要求的区间元素的个数，我们直接使用定义的两个下标相减，看看这个+1，-1细节的处理一下即可；

#include<iostream>using namespace std;const int N=1e5+10;int n;int a[N];int binary_search(int x,int y){    int left=1,right=n;    while(left<right)    {        int mid=(left+right)/2;        if(a[mid]>=x) right=mid;        else left=mid+1;    }        if(a[left]<x)    {        return 0;    }        int temp=left;        left=1,right=n;    while(left<right)    {        int mid=(left+right+1)/2;        if(a[mid]<=y) left=mid;        else right=mid-1;    }        if(a[left]>y) return 0;    return left-temp+1;}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        cin>>a[i];    }        int q;cin>>q;    while(q--)    {        int x,y;cin>>x>>y;        cout<<binary_search(x,y)<<endl;    }    return 0;}

2.A-B数对

下面的这个题目我们之前是有写过的，是在哈希表的文章里面，当时是使用的这个哈希表进行统计的；这次我们使用这个二分的思想进行求解；下面的这个就是我们的对应代码：

1）首先根据这个题目里面的数据范围确定这个数据的类型应该是这个Longlong类型的；

2）不断的进行这个数据的输入，因为这个输出的是c，我们想要求解的事这个a-b符合要求的数组的组数，因此我们只需要使用这个a-c，看看这个里面有多少个符合要求的a-c即可，这样，我们就可以把这个题目转换为我们在这个数组里面去找到这个a-c出现的次数即可；

3）上面我们已经知道了这个题目如何去使用这个二分的四星阿哥，记下来就是实现的问题，因为我们的这个a放到这个数组里面去啦，我们需要使用二分去查找是a-c，在下面的这个代码里面，我们使用b来进行的这个定义，因此只需要去这个数组里面找到这个b即可；

4）ret就是进行的这个相关的符合条件的这个数据的个数的统计，我们使用的不是传统的这二分的思路，而且调用的STL里面的两个函数，也就是upper_bound函数和我们的lower_bound函数；

我们直接进行两个函数的返回值的相减，得到的就是这个符合要求的数据的个数，里面的函数参数诸如这个a+i实际上利用的就是指针的指向的问题，为什么这个最开始是从a+1开始的，因为这个我们进行数据输入的时候就是从1开始的，因此我们寻找这个符合要求的数据个数的时候也是从下标为1的元素开始的；这个是需要我们注意的这个地方；

#include<iostream>#include<algorithm>typedef long long LL;const int N = 2e5 + 10;LL n, c;int a[N];using namespace std;int main(){    cin >> n >> c;    for (int i = 1; i <= n; i++)    {        cin >> a[i];    }    sort(a + 1, a + 1 + n);    LL ret = 0;    for (int i = 2; i <= n; i++)    {        LL b = a[i] - c;        ret += upper_bound(a + 1, a + i, b) - lower_bound(a + 1, a + i, b);    }    cout << ret << endl;    return 0;}