python - 二分查找

a = [1,3,5,7,9]
# 查找第一个大于等于x的位置
def lower_bound(l, r, x):
    while l <= r:
        mid = (l+r) // 2
        if a[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return l

# 查找第一个大于x的位置
def upper_bound(l, r, x):
    while l <= r:
        mid = (l+r) // 2
        if a[mid] <= x:
            l = mid + 1
        else:
            r = mid - 1
    return l

print(lower_bound(0, 4, 5))  # 2
print(upper_bound(0, 4, 5))  # 3