有序列表：唯一化与查找
看完你能徒手画出插入与删除每一步指针变化并说清边界情况
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
有序列表：唯一化与查找
看完你能徒手画出插入与删除每一步指针变化并说清边界情况
什么是有序列表
查字典时你敢直接翻到中间，是因为确定字按拼音排过序。有序列表就是这种「排好队」的存储：元素按大小依次摆放，查找因此有了质变。
字典按拼音排页码，对应列表按下标定位元素
有序 vs 无序
都叫列表，但一个对顺序有承诺、一个没有，这决定了你能做什么操作。
- 顺序即信息：位置有含义
- 可二分查找：O(log n)
- 插入删除需保持序，成本高
- 顺序无意义：仅是存放次序
- 只能线性扫描：O(n)
- 插入删除随意，成本更低
唯一化·构思
上一页说过，有序列表的元素按大小排好了队。排队有个副产品：值相同的节点只能紧挨着坐在一起。于是「去掉重复」这件在无序表里很麻烦的事，在这里变得出奇地简单。
书按类别排好后，同名书必并排，巡一遍书架即可清点
唯一化的推进过程
一次线性扫描，p 逐个前进，只和前驱比较，遇重复即摘除。
唯一化·实现
用 Python 把“比较、判断、摘除”三步写成真实可运行的 dedup 循环。
有序性保证重复元素必相邻，所以只需比较 nums[i] 与后一个；发现相等就 pop 摘除且 i 不动，因为新邻居可能仍重复。
唯一化的复杂度与边界
主路径是双指针唯一化：q 是读位置，慢指针是写位置；下方两条是特殊边界分支。
有序列表的查找接口
前面唯一化已经把重复元素清理干净，列表变得规整。那怎么在这样一串有序数字里快速找到目标？查字典时你不会从第一页翻起，而是直接翻到中间——这就是 search 接口的起点。
字典翻到的页码对应 search 返回的插入位置
二分查找的推进
二分查找每轮只做一件事：看中点，砍一半，直到目标无处可藏。
查找的边界情形
沿箭头读：每次比较走一条分支，最后看区间是否变空来区分命中、失败与边界返回。
有序查找 vs 无序查找
都叫"查找"，成本却差一个数量级：区别不在算法写法，而在列表结构承诺了什么。
- 顺序扫描，逐个比对
- O(n)：n 变大成本线性涨
- 数据乱放，任何元素都可能命中
- 取中点折半，排除一半
- O(log n)：翻倍只多查一次
- 有序承诺：比中点即知在哪半边
自测：唯一化与查找
对有序列表做二分查找，为什么每比较一次就能排除一半元素？
要点收束
- ✓有序性是前提：查找快，依赖元素已排序
- ✓唯一化靠相邻比较，一遍扫描即可完成
- ✓有序把查找从逐个比对变为二分折半
- ✓有序性、唯一化、查找互为因果的闭环
课后思考
先自己想几分钟，再对照参考答案；这些题没有唯一解。
参考答案有序后重复元素必相邻，一遍扫描即可完成；无序时要么两两比较（O(n²)），要么先排序再扫——代价转移到了排序那一步，整体仍是 O(n log n)。
参考答案每次剩原来的比例 k，迭代次数是 log 底 k 的对数，仍是 O(log n)。底数只是常数因子，渐近界不变——对数界对分割比例不敏感。
参考答案链表即使有序，也无法 O(1) 访问中位元素，二分退化。有序高效的前提是随机访问；有序性本身不自动带来效率，还要配上合适的存取方式。