Summary 当你你手里有一本厚厚的电话簿,要找"张伟"这个名字。你会从第一页一页页翻——还是会直接翻到中间,看看翻到的是"李"还是"王":姓氏排在"张"前面就往后翻,排在后面就往前翻。每翻一次,剩下要找的范围就少一半。一千页的电话簿,最多翻十次就能定位。 这就是二分查找的全部思想:在一个有序的范围里,每次砍掉一半...

Summary 排序看起来是个"把一堆数从小到大摆好"的小学生问题,但是它是算法入门里性价比最高的一站。 学习这个算法需要建立三种直觉: 分治(把大问题切成小问题再合并) 复杂度(为什么有的 O(n²) 有的 O(n log n),差在哪) 稳定性(相等元素的相对顺序会不会被打乱)。 这三样东西后面到处都用得上——快...

Summary 前面讲队列的时候,规则是"先进先出"——排队买票,来得早的先走。但现实里大量场景不讲先来后到,只讲谁最急:医院急诊室按病情严重程度排,操作系统按优先级调度进程,定时任务按到期时间触发。 这类需求抽象出来是同一个操作:在一堆动态变化的数据里,随时取出"最小(或最大)的那一个"。堆就是为这个操作而生的结构...

Summary 前面的数组、链表、栈、队列都是"一条线"——每个元素最多一个前驱、一个后继。但现实世界大量是层次关系:文件系统的目录树、公司的组织架构、HTML 的 DOM、区块链的 Merkle 树。树就是描述这种"一对多"层次关系的结构。更重要的是,树把查找从线性结构的 O(n) 压到了 O(log n)——这是...

Summary 用一个函数直接"算"出元素在哪，一步到位 O(1)。它的灵魂就一句话:哈希表 = 数组 + 一个把 key 变成下标的哈希函数，用"算地址"代替"找元素"。代价是天下没有免费的午餐:key 无限、桶有限，冲突必然发生，于是又牵出拉链法/开放寻址两套解决方案，以及装载因子 + 扩容 rehash 这套动...