Hello 算法 1.2 精讲：算法、程序与数据结构究竟是什么

先明确问题，再讨论怎样解决

算法是一套解决特定问题的可执行规则；数据结构组织数据及其关系，并提供可用的操作；程序用具体语言表达这些规则和操作。本节把这三个层次放到同一个小问题中观察。

这里使用有限的普通整数列表，讨论确定性查找。不同输入范围、随机化规则或外部状态，需要额外写清楚，不能从这一示例直接推广所有算法。

知识点 01—03：输入、输出与前提构成问题规格

“查找数字”有多种含义：判断是否存在、返回任意位置、返回第一次出现的位置，答案要求并不相同。我们先确定本节的任务：输入一个有限整数列表和目标整数；找到时返回最早匹配索引，找不到时返回 None；不修改输入。

重复元素、空输入和缺失目标都是合法输入，算法必须定义这些情况下的答案。负索引、None 与索引 0 也有不同含义；不能用含糊的“失败就返回一个数”替代明确的接口约定。

知识点 04：算法规则与 Python 程序的关系

算法规则可以用自然语言描述：从左向右检查；相等就立即返回当前位置；全部检查后仍不匹配，就报告未找到。Python 程序则把“逐个检查”写成 for，把“相等”写成比较，把“交回答案”写成 return。

同一套规则可以用不同语言实现，也可以有多种写法。反过来，代码能运行只说明语法和执行路径可用；是否解决了约定问题，还要检查结果、边界以及需要维持的性质。

下面四个结果依次为 0、1、None、None。返回 0 是成功找到的合法结果；使用结果时应检查 position is not None，因为 0 在真值判断中为假。

def first_index(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return None

print(first_index([10, 20, 10], 10))
print(first_index([10, 20, 10], 20))
print(first_index([10, 20], 99))
print(first_index([], 10))

知识点 05—06：为什么正确，为什么能够结束

每次即将检查索引 i 时，此前索引 0…i−1 都已经检查过且不匹配。这就是当前过程的不变量。若 values[i] 等于目标，所有更早位置都已经被排除，所以返回 i 满足“第一次出现”的要求。

如果循环耗尽，所有位置都不匹配，返回 None 正确。合法输入的长度为 n，未检查元素个数最多 n；每次继续检查都减少 1，或者通过 return 提前退出，因此这条过程在有限次比较后结束。

正确性与终止性要分别说明：一个总能退出的程序也可能返回错误答案；一个存在正确答案的过程也可能因为更新规则错误而永远找不到它。测试核验具体输入，不变量和推进理由解释整个约定输入范围。

知识点 07：确定含义与随机化的边界

本节算法的步骤和比较结果有确定含义。在列表、目标和运行条件保持一致时，结果一致。需要把“条件保持一致”展开：如果输入被其他代码改变、比较函数有外部副作用，或过程依赖随机选择，不能只用一个相同参数名推断整个过程相同。

延伸依据：Python 随机状态与可复现性 ↗。这是对原文简化描述的补充。

知识点 08—10：数据结构包含内容、关系和操作

数据结构除了记录值，也规定如何组织值，以及能用哪些操作访问、添加、删除或修改它们。列表体现一段有顺序的数据；字典体现键到值的映射；图可以表达对象之间的连接关系。逻辑关系与具体内存实现还要分别考虑。

例如，测试记录的内容包含用例 ID 与结果；关系可以是执行顺序，也可以是 ID 对应结果；操作则包括按顺序浏览、按 ID 查找、更新结果。不同表示支持不同的操作方式。

“空间尽量少、操作尽量快”是需要权衡的设计目标。为按 ID 查询建立额外索引会增加存储和维护工作；如果只读一遍，建立索引未必划算。没有一种数据结构能在所有操作与约束下同时最优。

知识点 11—12：组织方式影响实现和维护成本

下面先把记录保存在列表中，逐条比较 ID；再建立字典索引，按键取得结果。两个示例查询都返回 failed。这个比较约定 ID 唯一；字典索引不能自动表达同一 ID 的多条历史记录。

构造索引有初始工作，数据改变后也需要更新它。是否值得构建，取决于查询次数、更新频率、内存预算与需要保持的语义。不要只看一次查询的代码行数。

下面的索引构建明确拒绝重复 ID，避免悄悄把一条记录覆盖掉。unknown ID 返回 None。更完整的哈希行为在第 6 章展开。

def find_status(records, target_id):
    for record in records:
        if record["id"] == target_id:
            return record["status"]
    return None

def build_index(records):
    index = {}
    for record in records:
        key = record["id"]
        if key in index:
            raise ValueError("record IDs must be unique")
        index[key] = record["status"]
    return index

records = [{"id": "case-1", "status": "passed"},
           {"id": "case-2", "status": "failed"}]
print(find_status(records, "case-2"))
print(build_index(records).get("case-2"))

知识点 13：比较操作前，先明确已知什么

原书提到链表修改与数组访问的权衡。理解这类比较时，要明确操作起点：已经拿到待修改位置附近的节点，还是需要先从头寻找位置？寻找工作与真正修改链接的工作不能混在一句“插入很快”里。

同样，图表达更多关系，但占用多少空间取决于边的数量和表示方式。不能仅根据“图”或“链表”这两个名字断言某个实际数据集的内存大小。

算法原理、抽象数据结构与 Python 容器实现细节分开说明，是本课程后续各章的固定要求。当前 Python 列表和字典语义可从官方文档核验，后续章节再逐步分析具体操作成本。

依据：Python 数据结构与操作 ↗。

本节复盘：规格、实现与证据对齐

1. 返回任意匹配位置和返回第一次匹配位置，为什么是不同的规格？
2. first_index 的不变量是什么，为什么能证明最早匹配？
3. 为什么 if position 会误判索引 0？
4. 字典索引为什么需要明确重复 ID 的处理规则？
5. 链表修改的比较，为什么要问是否已经定位到节点？

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