004二分排序

在002，003，004几个算法（分治算法）中都用到了mid这一个变量，即mid=low+high >> 1 或者mid = low + high + 1 >> 1。二者的区别就是，前者可以取到左边界，后者可以取到右边界。这一个注意事项是，边界问题的关键因素，在整数排序中，需要时刻注意边界问题

上实例

思路分析

1. “查询”是查询某一个数的下表范围，而该序列是升序（有序的），所以仅需要查找左边界和右边界。
2. 边界：通过使用二分查找的思想确定边界。这里同样使用mid这个思想：
   1. 确定左边界，p[mid] >= x 说明在mid这一下标在x片区的右边界之右，所以x片区在mid左侧，故我们把r指针左移。令r = midmid也可能包含在x的范围中，因为我们判断条件是 >= ；反之，即mid<x，此时x的片区在mid的右侧，此时不包含mid这个下标，故 l = mid + 1 。注意点，因为确定左边界，但是我们移动的是r指针，为避免边界问题，导致死循环，需要保证mid不会取到右边界，即令 mid = l + r >> 1
   2. 如果x的片区不存在，在 a. 的循环步骤中，l与i相等，如果 p[l] != x 则返回 -1 -1
   3. 确定右边界， p[mid] <= x 说mid这一下标在x片区的左边界之左，所以x片区在mid右侧，故我们把l指针右移。令 l = mid，反之，即p[mid] > x 说明mid在x片区的右边界之右，所以x在mid的左侧，令 r = mid - 1 注意点，因为确定右边界，，但是我们移动的是l指针，为避免边界问题，使得l指针可能指向自己本身而导致死循环，需要保证mid不会取到左边界，即令 mid = l + r + 1 >> 1 实质上就是向上取整和向下取整的关系导致的边界取值问题

#include <iostream>
using namespace std;
const int N = 100010;
int main (){
    int n,q,a[N];
    cin >> n >> q;
    for( int i = 0; i < n; i++ ) scanf("%d", &a[i]);
    while( q -- ){
        int x;
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while(l < r){//找左边界
            int mid = l + r >> 1;
            if(a[mid] >= x) r = mid; //如果mid指向的值大于x，则说明左边界在mid左侧，需要把r左移
            else l = mid + 1;//同上，若mid小于x，则说明，左边界在mid右侧，需要把l移动到mid+1（a[mid]!=x，所以排除mid）
        }
        if( a[l] != x) cout << "-1 -1"<< endl;
        else{
            cout << l << ' ';
            int l = 0, r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}