C++ – BS 二分查找

可以将有序数列中的查找操作的时间复杂度优化到log N级别

数列为T获取查找部分的开头下标[start]和结束下标[end]以及要查找的数[x]

计算中间平分点下标[mid],即start和end的平均数

如果数据x在mid的左边就设end为mid重复以上操作,在右边反之

int bs(int start, int end, int x) {
    if(start >= end) return start;
    int mid = (end + start) / 2;
    if(queue[mid] >= x) return bs(start, mid, x);
    return bs(mid + 1, end, x);
}

STL

int fReturn = lower_bound(array, array + m,  x) - array;  //包括等于
int fReturn = upper_bound(array, array + m,  x) - array;  //不包括等于