//在arr中区间[lef,rig)寻找第一个>=val的元素的位置
//若没有元素>=val，则返回rig
int lowerBound(int *arr,int lef,int rig,int val)
{
    int mid;
    while(lef<rig)
    {
        mid=lef+((rig-lef)>>1);
        if(arr[mid]>=val)
        {
            rig=mid;
        }
        else lef=mid+1;
    }
    return lef;
}
//在arr中区间[lef,rig)寻找第一个>val的元素的位置
//若没有元素>val，则返回rig
int upperBound(int *arr,int lef,int rig,int val)
{
    int mid;
    while(lef<rig)
    {
        mid=lef+((rig-lef)>>1);
        if(arr[mid]<=val)
        {
            lef=mid+1;
        }
        else rig=mid;
    }
    return lef;
}
//在arr中区间[ lef,rig ]寻找等于key的元素
//不存在，则返回-1
int binarySearch(int *arr,int lef,int rig,int key)
{
    int mid;
    while(lef<=rig)
    {
        mid=lef+(rig-lef)/2;
        if(arr[mid]==key) return mid;
        if(arr[mid]>key) rig=mid-1;
        else lef=mid+1;
    }
    return -1;
}