二分查找

bsearch.py

def lower_bound(array, first, last, value): # 返回[first, last)内第一个不小于value的值的位置
    while first < last: # 搜索区间[first, last)不为空
        mid = first + (last - first) // 2  # 防溢出
        if array[mid] < value:
            first = mid + 1
        else:
            last = mid
    return first  # last也行，因为[first, last)为空的时候它们重合