第1章算法简介

从简单查找到二分查找，完整建立有序前提、low/high闭区间、命中与缺失返回、循环不变量，以及O(1)到O(n!)的增长率语言。

从四十亿到三十二步开始

先预测：在40亿个排好序的号码中找一个号码，简单查找最坏要检查40亿次；二分查找大约要多少次？

答案约为32次，因为2³²已经超过40亿。第1章用这个差距建立全书的两条坐标：一条是“算法是否解决问题”，另一条是“输入扩大后还能否及时解决”。是一组完成任务的指令；同一问题常有多种算法，结果相同但增长率可能完全不同。

问题求解先问输入、输出和前提。性能分析再问输入规模n增加时，比较、移动或存储等关键操作怎样增长。第1章不要求用秒表背某台电脑的数字，而是学习用大O语言比较增长。

二分查找的前提与契约

是的核心前提。若数据无序，中间值比目标小并不能推出目标在右边。

二分查找接收一个有序列表和目标item，输出一个命中下标；若目标不存在，返回None。重复元素存在时，原始版本只保证返回任意一个命中位置，不自动保证最左或最右位置。若业务要求首个命中，契约和边界更新都要改变。

采用闭区间[low, high]：

low=0指向第一个元素；
high=len(list)-1指向最后一个元素；
只要low<=high，区间中仍至少有一个候选；
当low>high，区间为空，目标不存在。

from collections.abc import Sequence
from typing import TypeVar
 
T = TypeVar("T")
 
def binary_search(values: Sequence[T], item: T) -> int | None:
    low = 0
    high = len(values) - 1
 
    while low <= high:
        mid = low + (high - low) // 2
        guess = values[mid]
 
        if guess == item:
            return mid
        if guess < item:
            low = mid + 1
        else:
            high = mid - 1
 
    return None

这个实现还隐含“元素与目标可使用同一全序规则比较”。数组或Python序列提供按下标随机访问；若在只能顺序移动的链表上每次寻找中点，O(log n)次比较不代表整体仍是O(log n)访问成本。

一次完整查找：目标13

在[1,2,...,15]中找13。第一次low=0, high=14, mid=7，猜到8，太小，因此low=8。第二次猜12，仍太小，low=12。第三次猜14，太大，high=12。第四次只剩下标12，猜13并命中。

是：如果目标存在，那么它一定位于闭区间[low,high]。当guess<item时，有序性说明low..mid全部不可能，故更新为mid+1不会漏掉目标；另一侧同理。

四种分支必须全部可达

新手常只用“目标正好在中间”的样例，导致缺失路径和边界错误没有暴露。至少测试：空列表、单元素命中、单元素缺失、首元素、末元素、中间元素和目标位于范围外。

def test_binary_search_boundaries() -> None:
    assert binary_search([], 7) is None
    assert binary_search([7], 7) == 0
    assert binary_search([7], 8) is None
    assert binary_search([1, 3, 5, 7, 9], 1) == 0
    assert binary_search([1, 3, 5, 7, 9], 9) == 4
    assert binary_search([1, 3, 5, 7, 9], 4) is None

简单查找与二分查找

每次只排除一个元素：

from collections.abc import Sequence
 
def linear_search(values: Sequence[int], item: int) -> int | None:
    for index, value in enumerate(values):
        if value == item:
            return index
    return None

最坏情况下，简单查找比较n次，二分查找每次把候选数至多减半。经过k次仍有至多n/2^k个候选；令它不超过1：

\frac{n}{2^k}\le1 \quad\Longrightarrow\quad k\ge\log_2n.

对非空长度n的闭区间实现，最坏比较次数可写成⌊log₂n⌋+1。因此8个元素最坏可能比较4次，而不是把“8连续减半三次得到1”误当成已经检查完最后一项。

若数据尚未排序且只查一次，先排序O(n log n)再二分通常不如直接线性查找O(n)。若同一份静态数据要查很多次，排序成本可以被后续大量O(log n)查询摊薄。算法选择必须把预处理、查询次数和更新频率一起计算。

大O记法比较增长率

不等于精确秒数，也不等于平均时间。第1章用它给出算法在输入扩大时的上界，让调用者知道性能不会差到哪里。

比某次小样本计时更稳定：

记号	直觉	典型例子
`O(1)`	输入变大，关键步骤仍有固定上界	数组按下标读取
`O(log n)`	输入翻倍只多约一步	二分查找
`O(n)`	输入翻倍，步骤约翻倍	简单查找
`O(n log n)`	每层处理全部元素，共对数层	高效比较排序
`O(n²)`	两层规模为n的工作	选择排序
`O(n!)`	枚举所有排列	旅行商穷举

写作O(1)；写作O(log n)；写作O(n)；写作O(n!)。

旅行商问题：阶乘爆炸

若用最直接方法枚举城市访问顺序，需要检查约n!种排列。城市从10增加到11，候选不是只多10%，而是乘以11：

10!=3{,}628{,}800, \qquad 11!=39{,}916{,}800.

这一例子不是要求第1章解决NP困难问题，而是让读者看到“算法增长率”比“电脑再快一点”更关键。若算法每秒检查一百万条路线，20个城市的20!仍远超可接受范围；必须利用问题结构、近似算法或约束规模，而不是只优化循环语法。

原章概念回查：一句话必须带条件

算法是一组完成任务的指令，但只有输入域、输出约定和结束条件明确时，指令才可执行。二分查找要求有序列表，因为比较中点后必须用顺序关系证明某一侧全部不可能；若只知道数据“通常有序”，算法仍可能排除真正答案。

在闭区间实现中，low和high标记剩余查找区间。每轮先检查中间元素，再根据比较结果严格越过mid；所以每一步排除一半候选，而不是把中点留到下一轮重复检查。目标不存在时，两个边界最终交错，空区间本身就是完整搜索失败的证据。

二分查找O(log n)，简单查找O(n)。大O记法描述增长率，大O给出最坏情况运行时间上界，却不会告诉你某次命中恰好用了几步。常见运行时间O(1)、O(log n)、O(n)、O(n log n)、O(n²)形成从易扩展到快速恶化的阶梯；还应继续记住旅行商问题与O(n!)，因为阶乘增长展示了“换更快机器”不能替代“换算法”。

把这些句子连起来，得到本章的决策顺序：先检查数据是否有序和可随机访问，再证明边界更新正确，最后用最坏增长率判断规模是否可承受。缺少任何一层，O(log n)都只是脱离前提的标签。

本章回顾：先保证正确，再比较增长

算法是一组有限明确指令，同一问题可有不同性能的解法。
二分查找要求有序、可比较且可高效按下标访问的序列。
low和high维护仍可能命中的闭区间。
中点猜小设low=mid+1，猜大设high=mid-1。
命中返回下标，low>high时返回None。
循环不变量证明边界更新没有排除可能目标。
简单查找每步排除一个候选，最坏O(n)。
二分查找每步排除约一半，最坏O(log n)。
大O描述增长上界，不是精确秒数或每次运行步数。
常见增长率从O(1)、O(log n)直到O(n!)差距巨大。
排序后二分是否划算取决于查询次数和数据更新频率。
旅行商穷举展示阶乘增长为何无法靠固定倍硬件升级解决。