从查找问题理解算法与数据结构

一份订单号列表里有重复值。现在要检查一个新订单号是否已经出现：直接扫一遍列表、建一个集合，或者先排序再二分，都能解决问题。区别在于准备数据、查找和更新分别要花多少工作，以及结果需要保留什么信息。

先把任务写清楚：输入是一组字符串 ID；查询只回答“存在或不存在”；允许原始数据重复；查询过程中暂不修改数据。这个约定让几种方法可以公平比较。若任务改为按提交顺序展示所有订单，或者统计每个 ID 出现了几次，数据结构也要跟着变。

复杂度描述的是规模增长

设列表有 n 个元素。顺序扫描在找到目标时可以提前结束，但查询一个不存在的值必须检查所有元素，最坏时间复杂度是 O(n)。这里先把一次字符串比较看作一个操作；字符串长度也随输入增长时，还要把比较的成本算进去。

若对 n 个新 ID 分别扫描一个同样规模的列表，工作量可能达到 O(n²)。O(n²) 描述的是增长关系，不是某个固定耗时。缓存、分配、字符串长度、实现语言和机器都会影响实际速度。小数据上更简单的方法可能已经够用，不能靠复杂度符号推算毫秒数。

空间成本要说明统计范围。顺序扫描只需要少量临时变量，额外空间是 O(1)，但原始列表本身仍占空间。说“算法只用常量空间”不代表整个程序没有随数据增长的内存。

集合为什么适合成员检查

Python 的 set 保存唯一元素，利用哈希值定位候选位置，再通过相等性判断确认元素。哈希冲突表示不同元素的哈希值可能相同，集合会处理这种情况；冲突不等于把不同订单号误认为同一个订单。

通常把集合的成员检查看作平均 O(1)。这个结论包含适用条件，不能变成任何输入下都恒定的时间保证。哈希计算、比较、扩容和冲突处理都有成本，最坏情况下查找也可能退化。ID 类型还要满足可哈希要求，列表这类可变容器不能直接作为集合元素。

集合会丢弃重复次数，也不承诺保留原始插入顺序。需要次数时可以用字典保存计数，或用 collections.Counter；需要顺序和去重时，应明确“保留第一次出现”还是“按 ID 排序”。Python 的 dict 保留插入顺序，不能把集合与字典混称为同一种行为。

二分查找依赖什么前提

二分查找在有序序列中反复缩小范围，一次定位需要 O(log n) 次比较。bisect_left 返回的是按当前排序关系插入目标的位置，不是“找到了目标”的布尔结果。位置可能在序列末尾，也可能指向一个比目标更大的值，所以必须检查位置是否有效、该位置的元素是否与目标相等。

建立有序列表先要排序，通常按 O(n log n) 估算。若数据稳定、查询很多，准备成本可以分摊；若只查一次，先排序可能比扫一遍做更多工作。不要在每次查询时重新排序后，又把整个查询流程称为 O(log n)。

Python 列表是可动态调整的数组式容器。在中间插入一个元素要移动后面的元素，仍可能需要 O(n) 工作。二分能更快找到插入位置，却不会消除移动成本。频繁更新、有序遍历和区间查询同时存在时，可以进一步评估树或数据库索引，但要计入它们的存储、维护和访问成本。

用同一份数据检查三种结果

示例先从重复 ID 建立集合，再得到有序的唯一 ID 列表。has 只针对这份已经排好的快照做二分查找。测试既包含存在的 O-1，也包含不存在且位于末尾之后的 O-4，后者能检查越界分支。

from bisect import bisect_left
ids = ["O-3", "O-1", "O-3", "O-2"]
ordered = sorted(set(ids))
known = set(ids)
def has(value):
    position = bisect_left(ordered, value)
    return position < len(ordered) and ordered[position] == value
for value in ["O-1", "O-4"]:
    assert (value in ids) == (value in known) == has(value)
assert len(known) == 3
print(ordered, has("O-4"))

运行后输出 ['O-1', 'O-2', 'O-3'] False。集合长度为 3，而原始列表长度为 4，说明重复次数已经丢失。三种查询对当前测试值给出了相同的存在性答案，不能据此说它们保留了相同的数据含义。

这是离线语义检查，没有测量性能，也没有连接订单数据库。多个请求并发创建订单时，“先查不存在，再插入”仍可能发生竞争。业务层的唯一性需要数据库唯一约束、事务和请求幂等等机制参与，进程内的集合不能替所有服务实例保证一致。

按操作需求选择结构

先列出高频操作及其约束，再选结构。只做少量成员检查，列表扫描容易实现和排错。大量重复查询而不需要顺序，可以评估集合。需要计数或通过 ID 取得记录，用映射表达键到值的关系。需要按顺序处理任务，队列比无序集合更贴近要求。

队列的选择也取决于具体容器。在 Python 列表头部删除元素会移动后续元素，collections.deque 更适合在两端频繁添加和移除。栈以“后进先出”为约定；图的邻接表表达节点之间的边。这些结构解决不同操作问题，不能排成一个统一的性能榜单。

如果数据持续变化，要写出索引怎样同步。更新原始列表却不更新 known 或 ordered，查询的就是旧快照。若多个结构共同表示同一份业务数据，维护成本和出错机会都会增加。能从一个权威来源派生的值，尽量不要让调用方分别修改。

练习：加入计数和更新

把示例改成一个小模块，提供存在性查询、出现次数查询和新增 ID 三个操作。保留原始列表作为权威数据，并明确辅助结构在初始化和新增时怎样更新。不要把“新增已经存在的 ID”当成没有变化，因为它会改变次数。

验收时加入空列表、只有一个元素、多个重复值、目标比最小值更小、目标落在两个已有值之间、目标比最大值更大，以及新增前后的查询。存在性结果应与直接扫描一致，次数应与原始列表的计数一致，有序辅助列表应持续满足排序约束。

最后分别记录初始化、查找和新增的工作量。需要性能结论时，在明确的数据规模、字符串长度、查询比例和运行环境下另做测量，把数据准备与查询时间分开报告。一次小示例的断言通过，只说明这些输入上的行为符合约定。