🏠 总目录📚 本教程 04 · 二分、排序与堆:怎样少看一半 ← →
📑 本页目录(点开跳转)

04 · 二分、排序与堆:怎样少看一半

⏱ 13 分钟 | 边界二分、旋转数组最小值、最小的 k 个数、复杂度增长

🎯 一句话

二分不是“猜中间数”,而是每一轮都能确定:答案还在左半还是右半。

🧩 题 1:升序数组中数字出现的次数

不要一个个数。找第一次出现的位置,再找第一次“大于目标”的位置;两者相减就是次数。

def lower_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left


def count_target(nums, target):
    return lower_bound(nums, target + 1) - lower_bound(nums, target)


assert count_target([1, 2, 2, 2, 3, 4], 2) == 3
assert count_target([1, 2, 3], 9) == 0
数组1、2、2、2、3、4中查找2的lower_bound,依次检查下标3、1、0,最终left和right都等于1。right可等于n,答案是插入边界,可为n;循环读取的下标仍小于n。
二分:找的是插入边界 — 沿用本题代码。实线边框是本轮读取区间,虚线是已排除读取的元素,暖色是 mid。闭区间边界候选包含 right;不要把“答案始终在 [left,right) 中”当成严格不变量。 单独打开图示

不变量:[0, left) 中都小于 target,[right, n) 中都大于等于 target;待判断元素位于 [left, right)。最终边界是 left == right,可能等于 n,因此插入位置属于闭区间 [0, n],不能说答案始终是半开区间里的元素。

🧩 题 2:旋转数组的最小数字

数组有重复值时,nums[mid] == nums[right] 不能判断最小值在哪半边;只将 right 减一,仍保留一个可能的最小值。无重复时每轮大致减半,是 O(log n);大量重复时最坏退化到 O(n)。空数组没有最小值,下面显式拒绝。

def min_in_rotated(nums):
    if not nums:
        raise ValueError("empty sequence")
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right -= 1  # 相等时无法判断哪半边,安全地缩小一个位置
    return nums[left]


assert min_in_rotated([3, 4, 5, 1, 2]) == 1
assert min_in_rotated([1, 2, 3]) == 1
assert min_in_rotated([1, 1, 0, 1]) == 0

🧩 题 3:最小的 k 个数

当你只要前 k 个,不必把全部排好。Python 的最小堆直接拿前 k 个最小元素。

import heapq


def smallest_k(nums, k):
    if not 0 <= k <= len(nums):
        raise ValueError("k out of range")
    return heapq.nsmallest(k, nums)


assert smallest_k([4, 5, 1, 6, 2, 7, 3, 8], 4) == [1, 2, 3, 4]

⚠️ 面试若要求手写,可用“大小为 k 的最大堆”;但先把“只维护 k 个候选”这个思想弄懂。

可选深入:同一处分区,递归与显式栈怎么写?

只把还没排好的区间交出去

本节的堆是在“只取 k 个”时少做工作;下面则假设需要完整排序,用快排作一个可跳过的对照。分区选末元素作 pivot,扫描时保持 [lo,i) ≤ pivot、[i,j) > pivot;最后把 pivot 放到 i,它就不再进入任何子问题。两种调度共用这一份分区,不要把分区边界和递归边界混用。

def partition(a, lo, hi):  # inclusive endpoints
    pivot, i = a[hi], lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

def quick_recursive(values):
    a = list(values)  # convenience copy; partition itself works in-place
    def visit(lo, hi):
        if lo >= hi:
            return
        p = partition(a, lo, hi)
        visit(lo, p - 1)
        visit(p + 1, hi)
    visit(0, len(a) - 1)
    return a

def quick_stack(values):
    a = list(values)
    pending = [(0, len(a) - 1)]
    while pending:
        lo, hi = pending.pop()
        if lo >= hi:
            continue
        p = partition(a, lo, hi)
        if lo < p - 1:
            pending.append((lo, p - 1))
        if p + 1 < hi:
            pending.append((p + 1, hi))
    return a

from itertools import product
for n in range(8):
    for values in product((-1, 0, 1), repeat=n):
        expected = sorted(values)
        assert quick_recursive(values) == expected
        assert quick_stack(values) == expected
for values in (list(range(30)), list(range(30))[::-1], [7] * 30):
    assert quick_recursive(values) == quick_stack(values) == sorted(values)
print("空/单元素/重复/有序/逆序与短数组穷举通过")

每次分区线性扫描当前区间;分得均衡时总工作 O(n log n),但这个固定末元素版本遇到已排序、逆序或全相同输入会退化到 O(n²)。递归深度最坏 O(n),在 Python 中还可能超过递归限制;显式栈移除了函数递归,没有自动消除坏分区,一般仍按最坏 O(n) 辅助调度空间估计。教学函数还额外复制了 O(n) 结果数组;两者都不是稳定排序。随机选 pivot 可改善期望行为,三路分区可改善大量重复值,但不在本小例展开。

依据作者教材:Open Data Structures:比较排序与快排。这里验证排序结果与边界,不提供生产排序性能结论。

📈 输入翻倍,时间为什么可能变四倍?

先看一个现象:同一个程序处理 200 个数据用了 200 秒。如果可用时间增加到 800 秒,能不能直接把输入也增加到 800 个?先别急着按比例乘四——答案取决于输入变大时,算法要做的工作怎样增长。

时间复杂度(Time Complexity)不是秒表读数。它比较的是:当输入规模 n 变大时,算法的主要操作次数按什么趋势增长。复杂度是在比较“输入变大后,工作量怎么长”,而墙上时钟测到的运行时间还会受机器、实现、缓存和当时负载影响。

先认清三个符号

先把线性增长和平方增长摆在一起

输入规模线性项主导的教学模型
工作量 ≈ cn
二次项主导的教学模型
工作量 ≈ cn²
直觉
nn(1 倍)n²(1 倍)作为比较起点
2n2n(2 倍)4n²(4 倍)在二次项主导模型里,输入翻倍对应约四倍工作
4n4n(4 倍)16n²(16 倍)在二次项主导模型里,输入变四倍对应约十六倍工作

读表时只比较教学模型里的倍数:线性增长看“一条边”,平方增长可想成正方形的长和宽一起变大。表格使用的是“线性项或二次项已经主导”的近似模型;不能从一个 O(...) 上界直接推出精确比例,更不是在声称每次运行都会精确花同样的秒数。

在二次项主导的模型中估算 800 秒能处理多少

要做下面的估算,不能只知道这个程序的上界写成 O(n²)。还必须假设两次运行使用同一台机器、同一份实现,输入足够大,并且从 200 个到待估规模这一段里,二次项确实压过固定开销和低次项。核心前提是:我们讨论的是二次项主导、可近似写成 t≈cn² 的输入区间;不是只看到 O(n²) 就套比例。

$$t \approx c n^2$$

第一次运行是 (n₁, t₁),第二次运行是 (n₂, t₂)。两式相除,公共的 c 被约掉:

$$\frac{t_2}{t_1}\approx\frac{c n_2^2}{c n_1^2}=\left(\frac{n_2}{n_1}\right)^2$$

这里继续用 ≈,因为 t≈cn² 本来就是二次项主导时的近似模型,而不是精确计时公式。

现在完整代入 n₁ = 200、t₁ = 200 秒、t₂ = 800 秒:

$$\frac{800}{200}=4\approx\left(\frac{n_2}{200}\right)^2$$

令 r = n₂ / 200,问题就变成 4 ≈ r²。平方根是在问:“哪个非负数自己乘自己得到 4?”因为 2×2=4,所以 4 的非负平方根是 2。虽然 (-2)×(-2) 也等于 4,但 r 是两个输入规模的比值,负的输入规模比例没有意义,因此这里只取非负的 2:

$$2\approx\frac{n_2}{200}\quad\Rightarrow\quad n_2\approx 2\times200=400$$

结论:仅在相同运行条件、且 200 到 400 这个输入区间可用 t≈cn² 描述时,时间预算变成 4 倍才对应输入规模约变成 2 倍,也就是约 400 个,不是 800 个。O(n²) 上界本身不够推出这个比例。

失败案例:把近似公式当成精确秒表

大 O 只给增长上界,不证明当前输入区间已经由二次项主导。如果输入只有几个元素,程序启动、函数调用、内存分配等固定开销可能比算法主体还显眼;换机器、换语言实现、缓存命中不同,甚至后台任务变化,也会改变墙上时钟时间。因此“工作量约四倍”不保证某次实测一定恰好从 200 秒变成 800 秒。这个比例估算只适合在同条件、同实现、较大输入且二次项主导时判断增长量级。

✍️ 预测练习:同条件且二次项主导时,时间预算变成 9 倍,输入能变成几倍?

只有在所比较的输入区间仍可近似写成 t≈cn² 时,才先写 9 ≈ (n₂ / n₁)²。3 是 9 的非负平方根,因为 3×3=9;输入规模比值不能为负,所以 n₂ / n₁ ≈ 3。若原来处理 200 个,大约可处理 600 个,而不是 1800 个。仅知道 O(n²) 上界时不能得出这个比例。

🔗 这一章连到哪里

去哪 为什么
不靠数据的 AI 07 · 启发式与 A* ⭐ 题 3 的 heapq 换个场景就是 A* 的心脏:按 $f = g + h$ 最小取出下一个节点,用的就是同一个最小堆

本节回顾

二分每轮都删掉一半,前提是你说得出删掉那一半为什么不可能有答案。

✅ 检查点

为什么 lower_bound 的右边界写成 len(nums) 而不是 len(nums)-1?

👀 看答案

因为要表达“目标比所有元素都大”时的插入位置;半开区间也让空数组和边界判断统一。

同一份程序在相同运行条件下,并且 300 到 600 这个输入区间的主要工作可近似写成 t≈cn²。输入从 300 个增加到 600 个时,主要工作量大约变成多少倍?为什么只知道 O(n²) 上界还不够?

👀 看答案

在题目明确给出的二次项主导近似下,输入变成 2 倍,主要工作量约变成 2² = 4 倍。O(n²) 只表示增长上界,并不保证当前区间由二次项主导;实际运行时间还受常数、缓存、实现、系统负载和固定开销影响,所以这个 4 倍仍不是精确计时承诺。


⚡ 走神救援

继续: 05 · 动态规划:把今天交给昨天

打卡记录保存在你的浏览器里,首页能看到总进度