04_二分查找

二分查找

在有序数组上查找

import bisect

arr = sorted([...])  # 先排序

# lower_bound: 第一个 >= x 的位置
pos = bisect.bisect_left(arr, x)

# upper_bound: 第一个 > x 的位置
pos = bisect.bisect_right(arr, x)

手动实现

# 查找左边界（第一个 >= target 的位置）
def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 查找右边界（第一个 > target 的位置）
def upper_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

在单调函数上查找

def last_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最大的 x 使得 f(x) = true"""
    lo -= 1
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # 向上取整
        if f(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

def first_true(lo: int, hi: int, f: Callable[[int], bool]) -> int:
    """查找最小的 x 使得 f(x) = true"""
    hi += 1
    while lo < hi:
        mid = lo + (hi - lo) // 2  # 向下取整
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo