查看“︁二分查找”︁的源代码

'''二分查找'''（binary search）在已经排好序的序列中寻找一个分界位置。查找“是否存在”只是它的一种用法：找到第一个不小于目标值的位置，便能同时处理重复值、插入位置和不存在的目标值。这里的输入是可按下标直接访问、按非降序排列的数列；输出是从 0 开始的下标。

== 一条有序数列的分界 ==
取 <math>a=(2,4,4,4,7,9,12)</math>，目标值为 4。下标 0 的值小于 4，从下标 1 起都不小于 4，所以'''左边界'''是 1；第一个大于 4 的数在下标 4，所以'''右边界'''是 4。等于 4 的元素恰占半开区间 <math>[1,4)</math>，出现三次。若改查 5，左右边界都等于 4：5 不在数列中，但应插在下标 4。

[[File:Gezhi-binary-search-boundaries.svg|frame|center|alt=有序数列二、四、四、四、七、九、十二的下标零到六；查找四时左边界为一，右边界为四，三个四位于半开区间一到四|左边界停在第一个 4；右边界停在 7 之前。相等元素占据两条边界之间的区间。]]

== 半开区间与查找过程 ==
只在 <math>[lo,hi)</math> 内保留尚未判定的位置。左边界查找始终保持两句话：<math>lo</math> 左侧的元素都小于目标值，<math>hi</math> 及右侧的元素都不小于目标值。初始 <math>lo=0,hi=n</math>，两边都没有已判定元素，因此条件成立。取 <math>mid=\lfloor(lo+hi)/2\rfloor</math>：
* 若 <math>a_{mid}<x</math>，从 <math>lo</math> 到 <math>mid</math> 都小于 <math>x</math>，把 <math>lo</math> 改成 <math>mid+1</math>。
* 若 <math>a_{mid}\ge x</math>，从 <math>mid</math> 到原 <math>hi</math> 的右侧都不小于 <math>x</math>，把 <math>hi</math> 改成 <math>mid</math>。

在上述数列中查 4，三次比较依次发生在下标 3、1、0。区间由 <math>[0,7)</math> 缩到 <math>[0,3)</math>、<math>[0,1)</math>、<math>[1,1)</math>。每次都丢弃至少一个位置；当 <math>lo=hi</math> 时，没有未判定的位置，两侧条件共同确定了第一个不小于 <math>x</math> 的下标。这个结束条件也覆盖空数列，此时直接返回 0。

== 重复值与未命中 ==
把比较条件改为 <math>a_{mid}\le x</math> 时，左侧留下的是“不大于 <math>x</math>”的元素，返回的是第一个'''大于''' <math>x</math> 的位置，即右边界。两个边界之差就是出现次数；左边界小于序列长度且该处恰等于目标值时，目标值才真正存在。只在遇到相等时立刻返回一个下标，无法保证它是重复值中的第一个。

排序条件不能省。若数列是 <math>(2,7,4)</math>，上面的左边界程序查 4 会返回下标 1，随后比较 <math>a_1=7</math> 而误判为“不存在”，尽管下标 2 存着 4。[[二分法]]则是在连续函数的异号区间内缩小求根范围；两者都对半缩小，但保持的条件不是同一件事。

<math-experiment type="algorithm" demo="binary-search" />

== Python 实现 ==
下面的两个函数不修改输入。<code>lower_bound</code> 与 <code>upper_bound</code> 分别返回左右边界；代码最后的断言就是正文数列的复算。

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo


if __name__ == "__main__":
    values = [2, 4, 4, 4, 7, 9, 12]
    assert (lower_bound(values, 4), upper_bound(values, 4)) == (1, 4)
    assert (lower_bound(values, 5), upper_bound(values, 5)) == (4, 4)
    assert (lower_bound([], 4), upper_bound([], 4)) == (0, 0)
</pre>
</div>

== 代价与使用范围 ==
每轮把候选区间至多缩为原来的一半，故比较次数为 <math>O(\log n)</math>，额外只用三个下标，为 <math>O(1)</math> 空间。这一时间界假定下标读取和比较都按常数成本计；链表无法像数组那样直接跳到中点。若要把元素插入 Python 列表，找到位置仍可用二分查找，但移动后续元素通常需要 <math>O(n)</math> 时间，不能把整个插入操作说成对数时间。

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/searches/binary_search.py TheAlgorithms/Python：binary_search.py]：同一仓库的左右边界等实现，本文代码和例子独立编写。
* [https://docs.python.org/3/library/bisect.html Python 标准库 bisect 文档]：左右插入点与重复值的约定。
* 先修：[[算法与复杂度]]；延伸：[[二分法]]、[[最短路径]]。
[[分类:算法]]