AI Agent Engineer

AI Agent Engineer

顺序、链式与二分查找

6 min read

顺序、链式与二分查找

本节目标

理解顺序结构为何擅长按位置访问、链式结构为何擅长在已知节点附近改链接，并能在“始终保持排序”的小型序列上正确使用 bisect。重点是操作取舍，不要求手写生产链表。

线性结构只有一个前后方向

在线性结构中，元素按一个序列排列。常见操作包括：

  • 按下标取得第 项；
  • 在开头、结尾或中间插入/删除；
  • 从头到尾遍历；
  • 按值查找；
  • 维护排序或只保留一个窗口。

“有顺序”不等于“已经排序”。消息列表按到达顺序排列；优先级序列按某个键排序；字典保持插入顺序但不是按键自动排序。

Python list 的实用模型

对常见 CPython，可以把 list 直觉化为可增长的对象引用数组：

  • 按下标定位通常为 ；
  • 尾部 append 通常为摊还 ；
  • 中间/头部插入删除要移动后续引用，通常为 ；
  • value in items 可能逐项比较，为 ；
  • 切片产生新的外层列表，代价随切片长度增长。

这是有用的实现成本模型，不是 Python 语言规范对每个实现的固定内存布局承诺。不要在教材中写死“每项多少 bytes”。

messages = ["system", "user", "assistant"]
first = messages[0]
tail = messages[1:]       # 新外层列表
messages.append("tool")  # 原列表尾部更新

链式结构的取舍

链表节点保存值和到下一节点（双向链表还含上一节点）的引用。若已持有目标节点，修改附近链接可为 ；但要找到第 项通常仍需从一端走 。

[A | next] → [B | next] → [C | None]

在普通 Python 业务代码中，手写链表常带来额外对象、引用和边界 bug，局部性也可能比顺序存储差。需要两端队列时优先 collections.deque；只有数据结构练习或确有节点级拼接需求时才实现链表，并用基准和不变量证明价值。

排序序列与二分边界

若序列已经按同一规则排序，二分法每次排除一半范围，查找边界为 。Python bisect 返回插入点，不直接判断相等：

from bisect import bisect_left, bisect_right
 
timestamps = [10, 20, 20, 35]
left = bisect_left(timestamps, 20)    # 1：第一个 20 之前
right = bisect_right(timestamps, 20) # 3：最后一个 20 之后
print(timestamps[left:right])         # [20, 20]

查找精确值时仍要检查边界与相等：

def find_exact(sorted_values: list[int], target: int) -> int | None:
    index = bisect_left(sorted_values, target)
    if index != len(sorted_values) and sorted_values[index] == target:
        return index
    return None

bisect 只依赖 < 来定位，不会验证输入真的有序。若排序键、大小写规则或数据在查找期间改变，结果不再可信。

insort 不是 O(log n) 插入

from bisect import insort
 
latencies = [80, 120, 250]
insort(latencies, 100)
print(latencies)  # [80, 100, 120, 250]

定位插入点为 ，但列表必须移动后续元素，所以 insort 总体通常为 。它适合小型、读取较多、偶尔插入的有序集合。若频繁按唯一键查找，用 dict；若只需反复取得最小优先级，用堆；若数据量或并发写入很大，应选择专门索引/存储。

官方文档也明确指出 bisect 函数不是线程安全的；并发修改同一序列可能得到未定义或失序结果。

Agent 工程例子

  • 用 bisect_left 找日志时间窗口的左边界；
  • 用 bisect_right 切出不晚于某阈值的已排序分数；
  • 小型有序候选集插入；
  • 不用它替代向量索引、数据库索引或优先级队列。

练习

  1. 对 [10, 20, 20, 35] 手算目标 5、20、40 的左右插入点，再运行验证。
  2. 写 within_range(sorted_values, low, high)，返回位于闭区间的切片且不修改输入。
  3. 比较列表和链表对“按下标读、已知节点后插入、整体遍历”的成本。
  4. 故意传入未排序列表，说明为什么“函数没有报错”不能证明结果正确。
  5. 为 find_exact 写空列表、首项、末项、重复值和不存在值测试。

自测

  • 能区分保序和排序。
  • 能解释 Python list 中间插入为何通常要移动元素。
  • 能说明链表 O(1) 插入隐含“已找到节点”的前提。
  • 能正确区分 bisect_left 与 bisect_right。
  • 不会把 insort 的总成本说成 。

下一步与相关概念

参考资料

获取日期：2026-07-14。

Backlinks