二分查找详解：原理、代码与时间复杂度

二分查找解决什么问题

线性查找逐个检查元素，最多需要 n 次比较。如果数据是有序的，可以做得好得多：把目标与中间元素比较，就能立刻知道应保留哪一半。这与在纸质词典里查单词是同一个思路。

二分查找也适用于任何具有单调性的情形，不限于数组。如果某个是/否条件对所有较小的值都为假，对所有较大的值都为真，二分查找就能找到这条分界线。这称为对答案二分。

分步示例

在有序列表 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]（下标 0 到 9）中查找 23。用两个下标 lo 和 hi 框定仍需检查的范围。

三次比较，而线性扫描需要六次。对于一百万个元素的列表，二分查找最多只需 20 次。

Python 实现

下面的迭代版本使用闭区间 [lo, hi]：两端都仍是候选位置。只要范围不为空，循环就继续。

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

在实际的 Python 代码中，请使用标准库模块 bisect。bisect_left 返回目标可以插入且保持列表有序的最左位置，由此也能判断目标是否存在。

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

时间与空间复杂度

变体：第一个、最后一个，以及对答案二分

许多问题问的不是某个值是否存在，而是边界在哪里：第一个不小于 x 的下标、x 的最后一次出现，或满足某个条件的最小数。使用半开区间 [lo, hi)，并且永远不要提前结束。

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• 下界（第一个值 ≥ x 的下标）：bisect_left。
• 上界（第一个值 > x 的下标）：bisect_right。
• 有序列表中 x 的个数：bisect_right(a, x) - bisect_left(a, x)。
• 在旋转有序数组中查找、寻找峰值，以及最小化最大值（例如在 D 天内运完所有包裹所需的最小运力），都是经典的面试变体。

常见误区

• 混用区间约定。闭区间应使用 lo <= hi 和 hi = mid - 1；半开区间应使用 lo < hi 和 hi = mid。混用会导致死循环或漏掉元素。
• 把 lo = mid + 1 写成 lo = mid。当 hi = lo + 1 时，mid 等于 lo，循环永远不会结束。
• 在无序数据上运行二分查找。它会返回错误答案，而且不报任何错误。
• 在 Java、C、C++ 等使用定长整数的语言中，(lo + hi) / 2 可能整数溢出。应使用 lo + (hi - lo) / 2。Python 的整数不会溢出，所以 (lo + hi) // 2 是安全的。
• 任务要求找重复元素中的第一次出现，却返回了第一个找到的匹配项。

何时使用二分查找

实际应用包括：数据库和文件系统的索引（B 树是这一思想的推广）、用 git bisect 找出引入 bug 的提交、在有序的区间表（如 IP 段）中查值，以及许多需要搜索阈值的数值问题。