标准库的实现

二分搜索.py

# 求左闭右开非降序区间 [left, right) 中第一个大于或等于 target 的位置
def lower_bound(array, left, right, target):
    while left < right:
        mid = left + (right -  left) // 2 # 防止溢出
        if array[mid] < target: left = mid + 1
         # if !(target < array[mid]): # 小于等于即为 upper_bound
        else: right = mid
    return left # 此时 left==right 成立