查找与排序：我真正容易混淆的几件事

复习查找和排序时，我发现最容易记住的是复杂度，最容易忘掉的却是前提。二分查找很快，但数据必须有序；哈希表平均查询很快，却不能自然解决范围查询。只背一个 O(log n) 或 O(1)，到了代码里还是会选错。

二分查找难在边界

顺序查找没什么神秘的，从头扫到尾即可。数据量不大、集合经常变化，或者只查一次时，它甚至可能是更省事的选择。

二分查找则适合已经排好序、而且会被反复查询的数据。我写它时最常出错的不是中间位置，而是 left、right 到底表示闭区间还是半开区间。下面这版使用闭区间，因此循环条件是 left <= right：

def binary_search(items, target):
    left, right = 0, len(items) - 1
 
    while left <= right:
        middle = left + (right - left) // 2
        if items[middle] == target:
            return middle
        if items[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
 
    return -1

真正要练的是把区间含义从第一行保持到最后一行，而不是默写某一份代码。

哈希表不是“永远的 O(1)”

哈希表的平均查找时间可以看作常数级，但它要付出额外空间，还要依赖合理的哈希函数和冲突处理。装载因子变高、冲突增多时，性能也会变化。

更重要的是它只擅长按键精确定位。如果问题是“找出 60 到 80 之间的所有成绩”，有序数组、平衡树或数据库索引通常比哈希表更合适。

排序时我会先问两个问题

第一个问题是数据规模和初始状态。插入排序最坏是 O(n²)，但数据很少或接近有序时，实现简单，额外开销也小。很多成熟排序实现会在小区间使用它，而不是只押注一种算法。

第二个问题是稳定性是否重要。假设先按姓名排好，再按分数排序；如果第二次排序稳定，同分记录仍会保留原来的姓名顺序。需要这种性质时，归并排序比典型的原地快速排序更容易满足要求。

这张表只适合做索引，不适合替代判断。真实项目里通常优先使用语言或标准库提供的排序，再根据数据特征、比较成本和内存限制决定是否需要自己实现。

现在回头看，这一章的重点不是记住“哪个最快”，而是看到一个问题时，能先说清楚输入是什么、结果需要什么性质，以及愿意拿什么资源去交换。