Hello 算法 1.1 精讲：从查找、整理扑克与找零看懂算法

从生活步骤，看见算法的结构

本节用查找、整理顺序和找零三个场景，理解算法的共同骨架：明确目标，保留当前状态，根据规则更新状态，达到停止条件后给出答案。先看到每一步在做什么，再给它们命名。

本章里的数据都很小，方便手工追踪。代码展示具体机制，不用一次运行的耗时判断谁更快；更完整的搜索、排序和贪心专题在后续章节单独展开。

知识点 01：把生活描述转成输入、状态和规则

“先做这个，再做那个”还不够。必须说明何时允许做、状态怎样改变、什么情况结束，以及最终结果要满足什么性质。生活比喻帮助建立直觉，转成程序时仍需要明确的输入约定。

知识点 02：有序信息为什么允许排除一半

假设数字按升序排列为 [3, 7, 11, 18, 25, 32, 40]，要找 25。中间数字是 18；因为左边所有数字都不大于 18，目标若存在就只能在右侧。因此可以一次排除一整段，不需要逐个检查它们。

如果中间数字大于目标，则排除它和右侧；若相等，返回位置。这种比较一次就缩小候选区间的方法叫二分查找。排除的依据是有序性。对任意乱序列表，同样的排除没有保证。

下面使用闭区间 [left, right]。left、right 是索引，不是元素值。mid=(left+right)//2 用整数除法取一个中间索引；列表从索引 0 开始计数。

知识点 03：把区间收缩写成 Python

函数前提：values 是有限、按升序排列的普通整数列表，target 是同类整数，搜索过程中列表保持不变。找到时返回一个匹配位置；没有找到返回 None。存在重复值时，这一版本不保证返回第一个匹配位置。

循环不变量是：如果目标存在且尚未找到，它一定仍在当前候选区间中。每次比较都保留可能包含目标的一侧；区间长度下降，最终找到或变空。trace=True 只负责打印当前状态，便于核验。

下面输出三次检查和 index 4。空列表初始 right=−1，直接返回 None。二分适合能低成本按索引读取的数据；每轮比较成本、预先排序成本和查询次数仍要分别考虑。

语言库对照：Python bisect ↗ 提供的是有序列表的插入位置，使用它判断元素是否存在时还要检查对应值。这里的区间不变量由本文代码推导。

def binary_search(values, target, trace=False):
    left, right = 0, len(values) - 1
    while left <= right:
        mid = (left + right) // 2
        if trace:
            print("bounds", left, right, "mid", mid, "value", values[mid])
        if values[mid] == target:
            return mid
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return None

values = [3, 7, 11, 18, 25, 32, 40]
print("index", binary_search(values, 25, trace=True))

知识点 04：插入排序怎样扩大有序前缀

取 [4, 2, 5, 3]。最左边只有一个元素，可以先视为有序。随后每轮取出一个新元素 key，把前缀中比它大的元素向右移，空出一个位置，再把 key 放进去。

不变量是：第 i 轮开始前，索引 0 到 i−1 的前缀已经有序，而且没有丢掉这些已处理元素。插入 key 后，有序前缀多包含一项。后缀未必有序，但会在之后的轮次逐项处理。

先保存 key 很重要：移动操作会覆盖它原来的位置。判断 j >= 0 在访问 result[j] 之前，还避免 Python 负索引把 −1 当成最后一个位置来读取。

知识点 05：移动、插入和输入是否被修改

下面先用 list(values) 复制列表，返回新的排序结果，原列表保持原来的顺序。比较使用严格大于号：与 key 相等的前缀元素不越过它，体现了插入排序可以保持等值元素原相对顺序的机制。

把数据复制进结果列表需要存储空间；不能看到内层只用了几个变量，就把这份返回列表的空间忘掉。已有序输入通常只需很少的移动，逆序输入则会产生更多移动。具体增长关系在排序章分析，这里先观察发生了什么。

def insertion_sort(values, trace=False):
    result = list(values)
    for i in range(1, len(result)):
        key = result[i]
        j = i - 1
        while j >= 0 and result[j] > key:
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = key
        if trace:
            print("insert", key, result)
    return result

values = [4, 2, 5, 3]
print("sorted", insertion_sort(values, trace=True))
print("original", values)

知识点 06：当前最好的选择，与最终最好是两个问题

给定金额 31 和面额 20、10、5、1，每次选择不超过剩余金额的最大面额：先取 20，剩 11；再取 10，剩 1；最后取 1。这种按当前局部标准作选择的策略叫贪心。

目前可以确认，它给出精确组合 [20, 10, 1]。但如果换成面额 4、3、1 和金额 6，同样策略得到 [4, 1, 1]，需要三枚；[3, 3] 只需两枚。规则能够执行且最终凑齐，不等于它对所有输入都使用最少枚数。

每种算法的正确性需要对照具体目标：如果目标只是凑齐金额，可行组合满足要求；如果要求枚数最少，还必须证明最优性。贪心能否满足最优目标，取决于问题结构，后续贪心章会进一步分析。

知识点 07：终止、可行解与失败信息

下面约定 amount 为非负整数，coins 是有限的正整数面额序列，面额可重复使用。排序和去重只用于确定选择顺序；每取一枚，remaining 至少减少 1，因此这条过程能结束。

没有面额 1 时，贪心可能剩下一点金额凑不齐。此时函数报告“这些贪心选择无法凑出精确金额”；这不是问题无解的证明。例如面额 4、3 和金额 6，贪心先取 4 后失败，但 3+3 是可行解。

下面分别输出一个正常示例和一个不最优的反例。精确凑齐、每个面额合法、是否最优，应分别检查。

def greedy_change(amount, coins):
    if type(amount) is not int or amount < 0:
        raise ValueError("amount must be a non-negative integer")
    if any(type(coin) is not int or coin <= 0 for coin in coins):
        raise ValueError("coins must contain positive integers")
    remaining = amount
    chosen = []
    for coin in sorted(set(coins), reverse=True):
        while remaining >= coin:
            chosen.append(coin)
            remaining -= coin
    if remaining:
        raise ValueError("greedy choices cannot make exact change")
    return chosen

print(greedy_change(31, [20, 10, 5, 1]))
print(greedy_change(6, [4, 3, 1]))

本节复盘：规则为什么能推进，答案满足什么

1. 二分查找为什么要求有序？把目标换成 26，候选区间如何变空？
2. 插入排序为什么先保存 key？怎样说明移动后没有丢掉元素？
3. 面额 4、3、1 找零 6，为什么贪心结果不是最优？
4. 一个算法能够停止、得到可行答案、得到最优答案，分别需要什么证据？

主题依据：krahets / Hello 算法原书 ↗。本文重新组织概念，加入原创代码、状态表、边界与复盘题；作者推导不等同于原文结论。改编文字采用 CC BY-NC-SA 4.0 ↗，保留署名、非商业使用与相同方式共享；此说明不更改本站其他内容或源码许可。