← 中文资源

简体中文版本

支持键函数的二分边界查找

在有序序列中查找下界与上界,支持可选键函数,并提供精确查找和重复元素计数。

阅读英文原文

功能说明

这组函数在已排序序列上做二分查找:lower_bound 返回第一个不小于目标的位置,upper_bound 返回第一个大于目标的位置,两者之差就是目标出现的次数;binary_search 返回任意一个匹配下标,找不到时返回 -1。它们支持通过 key 从元素中提取可比较字段,因此可以直接在按年龄排序的字典列表、按时间排序的记录或自定义对象上查找。

与 Python 标准库 bisect 相比,这里的实现显式展示边界逻辑,并且接受关键字形式的键函数,便于教学和定制。对包含重复元素的序列,边界查找比普通二分更有用:它不会随机返回中间某个匹配项,而是稳定地给出插入区间。

关键代码

下界在中间值小于目标时移动左边界,否则移动右边界:

while low < high:
    middle = (low + high) // 2
    value = key(items[middle]) if key is not None else items[middle]
    if value < target:
        low = middle + 1
    else:
        high = middle
return low

上界只需把比较改为 value <= target,其余结构相同。

使用注意

序列必须已按与比较逻辑一致的顺序排序;函数不会验证顺序,乱序输入会返回未定义结果。key 必须对每个元素返回可比较的值,且不能修改序列。对于降序序列,需要反转比较逻辑或先排序,不能直接复用。序列应支持 len 和整数下标,生成器需要先转成列表。

lower_bound 返回的插入位置可能等于序列长度,表示目标比所有元素都大。binary_search 只返回一个匹配位置,不保证是最左或最右;需要稳定位置时应使用下界。浮点数比较要留意 NaN,NaN 与任何值比较都为 False,会破坏二分假设。count_equal 需要调用两次边界查找,复杂度仍为 O(log n)。

验证方式

示例在 [1, 3, 3, 5, 8] 上查找 3,下界为 1、上界为 3,计数为 2;查找 5 返回下标 3,查找不存在的 4 返回 -1。对按年龄排序的记录列表使用键函数查找 36 返回 1,查找 55 返回 2。对字符串列表查找 blueberry 应返回插入位置 1。可以再加入重复记录,验证计数和边界稳定性。