我的刷题笔记:速记二分查找

in 刷题笔记 with 0 comment
def lower_bound(arr, left, right, value):
    """ 返回[left, right)范围内首个大于等于value的值的索引(下界) """
    while left < right:
        middle = left + (right - left) / 2
        if arr[middle] < value:
            left = middle + 1
        else:
            right = middle
    return left

def upper_bound(arr, left, right, value):
    """ 返回[left, right)范围内首个大于value的值的索引(上界) """
    while left < right:
        middle = left + (right - left) / 2
        if arr[middle] <= value:
            left = middle + 1
        else:
            right = middle
    return left

def equal_range(arr, left, right, value):
    """ 返回[left, right)范围内等于value的值的索引范围(右边界不包含) """
    return (
            lower_bound(arr, left, right, value),
            upper_bound(arr, left, right, value)
        )

参考经典回答 二分查找有几种写法?它们的区别是什么? 整理。
参考C++ 库二分查找实现lower_boundupper_bound

Responses