算法题（139）：牛可乐和魔法封印

审题：
本题需要我们将数组中包含在区间x~y之间的数据个数找到并输出

思路：
方法一：暴力解法

首先我们可以直接遍历一次数组，找到x的索引，然后再找到y的索引，并计算最终的元素个数，这里就要有O（n）的时间复杂度，且由于是多组数据又要进行q次。综上，时间复杂度为O（nq），而n为1e5,q为1e5，运行次数就要达到1e10.一定会超时

方法二：二分查找

对于左边界，我们可以将数组划分为小于x和大于等于x的区域。对于右边界，我们可以将数组划分为大于y和小于等于y的区域。

这就说明数组的划分具有二段性，此时我们就可以分贝对x和y进行二分查找了

对于寻找大于等于x的左边界：
1.mid的计算：(left+right)/2

因为是要让right靠近left寻找左边界

2.更新策略：
当a[mid]小于x的时候，说明mid前面包含自身的索引区域都不是左边界的候选区域了，直接让left=mid+1.

当a[mid]大于等于x的时候，虽然mid右边区域是大于等于x边界的区域，但是一定不是最左的边界了，所以让right = mid，之所以不能等于mid-1，是因为mid有可能是左边界

3.尾处理

若最终left等于right后的索引对应的数据值是小于x的，说明数组中所有数据的值都是小于x的，此时一定没有数据落在我们的x~y区间中，直接输出0，然后进入下一组判断即可

对于寻找小于等于y的右边界：
1.mid的计算：(left+right+1)/2

2.更新策略：原理与左边界查找一样

3.尾处理：判断a[left]是否大于y，若大于说明数组中没有数据落在区间x~y之间，也是输出0并进行下一组判断

解题：
 

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,q;
int a[N];
int x,y;
int main()
{//数据录入cin >> n;for(int i = 0; i < n; i++){cin >> a[i];}cin >> q;//多组数据二分查找while(q--){cin >> x >> y;int mid = 0;//查找大于等于x的左边界int pos1 = 0;//左边界ll left = 0;ll right = n-1;while(left < right){mid = (left+right)/2;if(a[mid] >= x){right = mid;}else{left = mid + 1;}}if(a[left] < x)//所有元素都小于x{cout << 0 << endl;continue;}else{pos1 = left;}//查找小于等于y的右边界int pos2 = 0;//右边界left = 0;right = n-1;while(left < right){mid = (left+right+1)/2;if(a[mid] <= y){left = mid;}else{right = mid - 1;}}if(a[left] > y)//所有元素都大于y{cout << 0 << endl;continue;}else{pos2 = left;}cout << pos2-pos1+1 << endl;}return 0;
}

若是正常的找到左右边界就用pos1或pos2记录下来最后进行计算然后输出

牛可乐和魔法封印