顺序查找与二分查找
复习
- 数组：连续存储，可按下标访问
- 动态数组：动态数组在容量不足时自动扩容
- 字符串：字符的序列
TL;DR
- 顺序查找逐个比较，代价
O(n) - 二分查找每次砍掉一半，代价
O(log n) - 二分查找必须依赖有序数据
- 它还依赖随机访问，因此链表上通常不划算
正文
有了数组，最常见的操作就是“在里面找一个东西”。这一章看看两种查找方式，它们的差距非常能说明问题。
顺序查找：老老实实挨个看
顺序查找（linear search）最朴素：从第一个开始，逐个和要找的目标比较，直到找到或看完。
- 最好情况：第一个就是，
O(1) - 最坏情况：找完都没有，
O(n)
它不需要数据有任何特殊排列，什么都能用。但数据一多，就慢。
二分查找：每次砍一半
如果数据事先排好了序，就能用更快的方法——二分查找（binary search）：
- 看中间那个元素
- 比目标小，就去右半边找；比目标大，就去左半边找
- 每次都能排除掉一半
数据量无论多大，每次都除以 2，所以很快到达。从 100 万个元素里找，最多也就约 20 次。这就是 O(log n) 的威力。
它的两个前提
二分查找这么快，却有两个硬性前提，缺一不可：
- 数据必须有序：否则“砍一半”的推理不成立，不知道该往哪边找
- 必须能随机访问：也就是能
O(1)地跳到“中间”那一个
第二条特别容易被忽略。数组可以随机访问，所以二分很合适；而链表虽然也能有序，却只能从头一个个走，跳到“中间”本身就要花 O(n)，二分的优势就没了。这也是为什么“算法好不好用”，往往取决于“数据结构支不支持”。
小心边界
二分查找思路简单，实现却很容易写错，尤其是各种边界：区间是左闭右开还是闭区间、循环什么时候结束、中点怎么算。“看起来简单”不等于“随手就能写对”，这正是需要仔细推导和验证的地方——就像前面强调过的，正确性得靠论证，而不是碰运气。
思考题 1
二分查找为什么必须要求数据有序？
思考题 2
为什么二分查找在链表上通常不划算？
小结
知识点
- 顺序查找
O(n)，不需要数据有序 - 二分查找
O(log n)，每次排除一半 - 二分查找要求数据有序且可随机访问
- 二分查找的边界条件容易出错
参考资料
- Wikipedia(zh)：线性搜索：逐个比较的查找方式
- Wikipedia(zh)：二分查找算法：每次排除一半的查找方式
思考题答案（仅供参考）
思考题 1
因为二分查找依赖“中间元素与目标的大小关系”来判断该往哪半边找。只有数据有序，这个判断才能成立；否则元素的大小分布没有规律，排除一半就可能把目标也排除了。
思考题 2
因为二分查找需要能 O(1) 地跳到中间元素。链表不支持随机访问，要到达中间位置必须从头逐个走，本身就要花 O(n)，把二分每步 O(1) 的优势抵消了，所以通常不如直接顺序查找。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪