数组与索引

数组把有序序列放在编号槽位中，通过从零开始的索引读取。长度为 n 的数组，合法非负索引恰好是 0 到 n - 1。range(len(values)) 遍历这些位置；索引 n 已没有对应槽位。

索引像尺上的坐标：槽位 0 的位移是 0，槽位 1 的位移是 1。坐标说明位置，不表示计算机的行走路线。数组直接计算目标位置，不从槽位 0 向右扫描。

数组与索引如何工作

在 values = [12, 7, 25] 中，索引 0、1、2 分别存放 12、7、25。索引关心位置，与值的大小无关。

非负索引 i 的边界条件是 0 <= i < len(values)。上界必须严格小于长度。长度为 3 表示有三个槽位，编号为 0、1、2；长度不是末尾索引。

range(len(values)) 因此适合遍历。range(3) 依次产生 0、1、2 后结束，不会赋值 i = 3，循环体也不会尝试 values[3]。

数组式表示中的一次索引读取是 O(1)。运行时结合起始地址、索引和一个引用槽位的宽度，直接计算目标位置。遍历所有元素仍是 O(n)，因为要做 n 次读取。

Python 计算 values[3] 时会抛出 IndexError，不会返回 None，也不会补出空单元。若这个表达式用作 print 参数，异常在调用 print 前就已发生。

逐步演示

默认使用 values = [12, 7, 25] 和 probe = 3。

1. 第 1 行准备 range(len(values))。长度为 3，候选索引是 0、1、2。
2. 循环产生 i = 0。第 2 行读取 values[0]，得到 12，打印 0 12。
3. 循环产生 i = 1。第 2 行读取 values[1]，得到 7，打印 1 7。
4. 循环产生 i = 2。第 2 行读取 values[2]，得到 25，打印 2 25。
5. 迭代器耗尽。i 仍是 2，不会被赋值为 3。执行离开循环，没有第四次读取。
6. 第 3 行判断 0 <= 3 < 3，结果为假。
7. 计算 values[3] 抛出 IndexError。参数求值中止，因此 print("probe", ...) 不会执行。

画面把两件事分开：先显示 range(3) 在 3 之前停止，再把探测位置移到同一个无槽位边界，实际越界读取才变红。地址提示是 base + 3 × one slot，表示一次计算就到达边界，没有扫描槽位 0、1、2。

索引为什么是 O(1)

这个 O(1) 结论依赖固定宽度引用槽位的数组式表示。链表需要从头沿链接走到位置 i，成本是 O(i)，不能用相同的直接定位方式。

边界情况

• 空数组。 len(values) 为 0，range(0) 不产生索引，所有非负探测位置都越界。
• 第一个槽位。 数组非空时，索引 0 合法，相对起点的位移为零。
• 最后一个槽位。 长度 n > 0 时，最后一个非负索引是 n - 1。
• 越过末尾。 n 是第一个非法非负索引，Python 抛出 IndexError。
• Python 的负索引。 -1 表示最后一个元素，直到 -n 表示第一个。本课主图使用非负索引，因为其他语言不一定支持这条规则。

常见错误

• 使用 i <= len(values) 作为遍历条件。等号允许访问已经越界的索引 n。
• 把长度当成末尾索引。非空数组应减一得到最后一个非负索引。
• 以为越界会返回 None。Python 会先抛出异常，外层调用可能根本没有执行。
• 想象 O(1) 索引从槽位 0 开始行走。运行时直接计算目标槽位。
• 在索引 n 处画空格子。那里没有槽位，应画边界，不能暗示还存在一个单元。

本课的简化

格子表示 Python 列表的逻辑槽位，不是内存转储。列表连续存放对象引用，整数对象本身不必相邻。画面省略字节地址、预留容量、扩容、对象头和解释器机制，主图也不演示负索引。其他语言可能触发陷阱、抛出不同异常或允许不安全访问；IndexError 是这里的 Python 行为。