二分总结

二分查找基本模板：查询一个有序数列中等于target那个数字的下标（在这里如果有多个target会怎么样？）

{
    while(low <= high){
        int mid= high - (high - low)/2;
        if( a[mid] < target )
            low = mid+1;
        else if( a[mid] > target)
            high = mid-1;
        else
            return mid;
    }
}

一.在target为多个的时候，查询等于target的第一个数的下标

int Bsearch_1(int a[],int low,int high,int target)
{
    while(low <= high){
        int mid= (high + low)/2;
        if( a[mid] < target )
            low = mid+1;
        else if( a[mid] > target)
            high = mid-1;
        else{
            if(mid == 0 || a[mid]!=a[mid-1])
                return mid;
            else
                high = mid - 1;
        }
    }
}

二.在target为多个的时候，查询等于target的最后一个数的下标

int Bsearch_2(int a[],int low,int high,int target)
{
    while(low <= high){
        int mid= (high + low)/2;
        if( a[mid] < target )
            low = mid+1;
        else if( a[mid] > target)
            high = mid-1;
        else{
            if(mid == high || a[mid]!=a[mid+1])
                return mid;
            else
                low = mid + 1; //
        }
    }
}

三.查询大于target的第一个数的下标

int Bsearch_1(int a[],int low,int high,int target)
{
    while(low <= high){
        int mid= (high + low)/2;
        if( a[mid] <= target )
            low = mid+1;
        else
            high = mid-1;
    }
    return low;
}

三.查询小于target的第一个数的下标

int Bsearch_4(int a[],int low,int high,int target)
{
    int mid;
    while(low <= high){
        int mid= (high + low)/2;
        if( a[mid] >= target )
            high = mid-1;
        else
            low = mid+1;
    }
    return high;
}

同三