算法知识图谱总览 / 排序与基础算法族 / 二分查找

二分查找

P0basicdeepG-A-1
← 上一个 / 组内tournament-sort 组内第 9 / 20返回组索引 全局返回总览 下一个 / 组内ternary-search

What · 是什么

有序数组 O(log n) 查找，含 lower_bound/upper_bound

二分查找（binary search，折半搜索）在有序数组中 O(log n) 定位元素。核心：每次取中值比较，据此丢弃一半区间。衍生变体：精确查找是否存在、lower_bound（首个 ≥ key 的下标）、upper_bound（首个 > key 的下标）。广义二分：单调布尔条件（满足/不满足）也是『有序』，因此可求『最后一个满足条件的位置』——这是二分答案的基石。迭代实现空间 O(1)。

Why · 为什么

直觉 · Intuition

猜数字游戏：每次问『目标是否 ≥ mid』，答案是非黑即白，区间一分为二。因为数组有序，一次比较能确定目标在左半边还是右半边，把搜索空间指数级缩小。

原理 · Principle

不变式：维护区间 [l, r) 使 l 及其左侧均满足条件 P、r 及其右侧均不满足（或相反）。每轮取 mid=(l+r)//2，若 P(mid) 成立则 l=mid（或 l=mid+1），否则 r=mid。循环终止时 l 就是『最后一个满足条件的位置』。lower_bound 用 P(x)=(a[x]>=key)，upper_bound 用 P(x)=(a[x]>key)。中值用 l+(r-l)//2 防止 (l+r) 溢出（Python 无此问题，但代码风格建议）。

历史 · History

二分查找思想可追溯至古代（数论与图书馆查书），现代首次成文是 1946 年 John Mauchly；1960 年 D. H. Lehmer 给出第一个无 bug 版本；1962 年发表论文。但它『简单而难写对』，1962 年 Knuth 即指出直到 1960s 才有人写出正确版本。1988 年 John Bentley 在《Programming Pearls》中统计：专业程序员中约 90% 首次写错。

How · 实现

伪代码

lower_bound(a, key):            # 首个下标 i 使 a[i] >= key，不存在返回 n
    l, r = 0, len(a)              # [l, r) 半开区间
    while l < r:
        mid = (l + r) // 2
        if a[mid] < key:
            l = mid + 1
        else:
            r = mid
    return l

upper_bound(a, key):            # 首个下标 i 使 a[i] > key
    ... if a[mid] <= key: l = mid + 1
        else: r = mid

binary_search(a, key):          # 精确查找
    i = lower_bound(a, key)
    return i < len(a) and a[i] == key

Python 实现

def lower_bound(a, key):
    """首个 >= key 的下标；全部小于 key 时返回 len(a)"""
    l, r = 0, len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] < key:
            l = mid + 1
        else:
            r = mid
    return l


def upper_bound(a, key):
    """首个 > key 的下标；全部 <= key 时返回 len(a)"""
    l, r = 0, len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] <= key:
            l = mid + 1
        else:
            r = mid
    return l


def binary_search(a, key):
    i = lower_bound(a, key)
    return i < len(a) and a[i] == key


def last_leq(a, key):
    """最后一个 <= key 的下标，不存在返回 -1（广义二分示例）"""
    l, r = 0, len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] <= key:
            l = mid + 1
        else:
            r = mid
    return l - 1


if __name__ == "__main__":
    import random
    for _ in range(300):
        n = random.randint(0, 60)
        a = sorted(random.randint(0, 30) for _ in range(n))
        key = random.randint(0, 35)
        # 与暴力对照
        assert lower_bound(a, key) == sum(1 for x in a if x < key), (a, key)
        assert upper_bound(a, key) == sum(1 for x in a if x <= key), (a, key)
        expect = key in a
        assert binary_search(a, key) == expect, (a, key)
        le = [i for i, x in enumerate(a) if x <= key]
        assert last_leq(a, key) == (le[-1] if le else -1), (a, key)
    print("lower_bound/upper_bound/精确查找/广义二分 全部正确 OK（300 组随机）")
    a = [1, 2, 2, 2, 3, 5, 8]
    print(f"a={a}, lower_bound(2)={lower_bound(a, 2)}, upper_bound(2)={upper_bound(a, 2)}")
    print(f"binary_search(4)={binary_search(a, 4)}, last_leq(4)={last_leq(a, 4)}")
PyPy 提示PyPy 下手写二分与内建 bisect 性能差异不大，但 bisect_left/bisect_right 更少出错，强烈建议直接用。Python 无整数溢出，mid=(l+r)//2 即可。大循环用 bisect 的 C 实现有优势。
时间复杂度O(log n)
空间复杂度O(1) 迭代；O(log n) 递归
注意 · 局限前提是数组有序（或条件单调）。非单调条件无法二分。写错多发生在边界：while l<r vs l<=r、mid+1/mid-1、l=mid vs l=mid+1 的组合。统一用半开区间 [l,r) 与 l=mid+1 策略可系统避免。

易错点

例题

OJ题号难度考点链接
LuoguP22492lower_bound 模板https://www.luogu.com.cn/problem/P2249
LeetCode704 / 342二分查找及查找区间端点https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
CP-Algorithmsnum_methods/binary_search3二分搜索有序数组官方教程https://cp-algorithms.com/num_methods/binary_search.html
步骤迷你图（节点 = 算法步骤 · 边 = 流程 · 绿色 = 起始步骤）
下游 · 依赖本知识点
二分答案前置依赖三分法变体WQS二分/凸优化DP组合

信源

✓ = 已核验 · △ = 未核验