二分查找 · aiwiki.page

二分查找是一种在已排序的数组（数据结构）中定位目标的算法：反复将目标与中间元素比较，并排除不可能包含目标的那一半。找到目标或不再有候选项时，查找结束。它是分治法的一种应用，不过每一步只继续处理划分后得到的一个子问题。如果元素访问和比较都能在常数时间内完成，其最坏情况下的运行时间与元素数量的对数成正比。(xlinux.nist.gov)

排序要求与查找过程

对于按升序排列的数组，将目标与中间元素比较会有三种结果。如果目标较小，只需继续考虑较小的那一部分；如果目标较大，只需继续考虑较大的那一部分；如果两者相等，精确匹配查找可以立即返回。与线性查找不同，二分查找不必先逐一检查某个候选元素之前的所有元素。它之所以能排除整个区段，前提是数组已按照查找时采用的比较规则排好序。(xlinux.nist.gov)

例如，在数组 [3, 8, 12, 17, 24, 31, 46] 中查找目标 24。最初的中间元素是 17，因此接下来只在 24, 31, 46 中查找。再与 31 比较后，排除较大的值，只剩下 24。这个例子说明，查找过程中索引边界不断收缩，而数组本身保持不变。(algs4.cs.princeton.edu)

二分查找适用于有序且可按索引访问的数据，并不要求数据采用某种特定的数值表示。记录可以通过用于比较的键来查找，但其存储顺序必须与该键的排序规则一致。对于降序序列，需要反转相应的比较方向。(go.dev)

边界查找的实现

一种实用的变体不会在遇到相等元素时立即返回，而是返回第一个值不小于目标的位置。这个位置称为下界（lower bound），也是一个能保持升序的插入位置。如果所有元素都小于目标，该位置就等于数组长度。(courses.cis.cornell.edu)

下面的伪代码采用从零开始的索引和左闭右开区间 [lo, hi)，即包含 lo，但不包含 hi：

lower_bound(A, x):
    lo = 0
    hi = length(A)

    while lo < hi:
        mid = lo + floor((hi - lo) / 2)
        if A[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    return lo

这里，floor 表示向下取整，结果为整数。若返回的位置为 p，则可通过检查 p < length(A) 且 A[p] == x 来确定目标是否确实存在于数组中。对于空数组，整个过程不会访问任何元素。(courses.cis.cornell.edu)

算法的正确性可以用循环不变量来表述：lo 之前的每个元素都小于 x，hi 及其之后的每个元素都不小于 x，并且 0 ≤ lo ≤ hi ≤ n。每次更新都保持这些条件成立。区间宽度始终非负且严格递减，由此可证明循环必然终止；当两个边界重合时，循环不变量便确定了所需的插入位置。这类推理是将形式验证和数学证明应用于程序行为的典型方式。(courses.cis.cornell.edu)

复杂度与数据表示

对于长度为 (n) 的非空数组，传统的精确匹配版本最多需要 (\lfloor\log_2 n\rfloor+1) 次迭代。反复折半使其时间复杂度为对数级，通常用大O记号写作 (O(\log n))。当访问和比较的成本均为常数时，每次迭代只需完成常数量的工作。(cs.princeton.edu)

迭代实现只需存储固定数量的索引，因此辅助空间复杂度为 (O(1))。使用递归的实现，如果每次调用都保留在调用栈上，通常会消耗 (O(\log n)) 的栈空间。这些复杂度界限针对的是查找过程本身，不包括输入数据的存储或预先排序的成本。(algs4.cs.princeton.edu)

数据结构的选择很重要。数组支持高效的随机访问，而在链表中定位中间元素则需要遍历。在有序链表上进行二分查找，比较次数仍可保持为 (O(\log n))，但总的遍历工作量可能达到 (O(n))。因此，对数级的比较次数并不一定意味着对数级的执行时间。(xlinux.nist.gov)

重复值与插入位置

存在重复值时，精确匹配实现可能返回任意一个匹配项。下界查找则定位第一个匹配项。与之对应的上界查找（upper-bound search）会找到第一个严格大于目标的元素。这两个边界共同界定了所有匹配元素所在的区间；将两者的索引相减，即可得到目标出现的次数。Python 的 bisect_left 和 bisect_right 分别提供了这两种插入位置约定。(algs4.cs.princeton.edu)

找到插入位置，并不意味着插入操作也具有对数级复杂度。在以数组为底层存储的序列中，插入一个元素可能需要移动与序列长度成正比的现有元素。因此，Python 的 insort 操作虽然查找步骤是对数级的，总时间复杂度仍为 (O(n))。(docs.python.org)

推广与实现中的常见陷阱

该方法可以推广到返回布尔值的函数：函数在起始的一段范围内为假，此后均为真。二分查找无需实际构建数组，就能找到第一个为真的位置。这是针对单调函数进行边界查找的一种形式；Go 的 sort.Search 明确接受这样的谓词，并在不存在为真的位置时返回搜索范围的长度。(go.dev)

边界约定必须始终一致：左闭右开区间与两端均闭合的区间，采用的终止条件和更新规则不同。错误的更新可能遗漏候选项，也可能使查找无法继续推进。另一个隐患是在计算 (lo + hi) / 2 时发生整数溢出。对于非负且处于可表示范围内的边界，使用 lo + (hi - lo) / 2 可以避免中间求和结果溢出。(cs.cornell.edu)