二分查找应用

实现

int BinarySearch(int a[], int size, int p)
{
    int L = 0; //查找区间左端点
    int R = size-1; //查找区间右端点
    while (L <= R)
    {
        int mid = L + (R-L) / 2;//正中元素的下标，总个数偶数时是第一个
        if (p == a[mid])
        {
            return mid;
        }
        else if (p > mid)
        {
            L = mid + 1;//设置新左端点
        }
        else
            R = mid - 1;//设置新右端点
    }
    return -1; //返回不存在的下标
}//复杂度是log(n)

int LowerBound(int a[],int size, int p){
    int L = 0;
    int R = size - 1;
    int lastPos = -1;//最近一次更新
    while (L <= R)
    {
        int mid = L + (L-R) / 2;
        if (a[mid] >= p)
        {
            R = mid - 1;
        }
        else
        {
            lastPos = mid;
            L = mid + 1;
        }
    }
    return lastPos;
}

注意：数组里必须是排好序的元素