线性查找与二分查找
线性查找（Linear Search） 是最朴素的查找方式——从头到尾顺序扫描，逐个比较，O(n)。它不要求任何前提：无序数组、链表、文件流都能用，是查找算法的「保底方案」。二分查找（Binary Search） 则建立在「有序 + 随机访问」两个前提之上——每次比较中点后，根据有序性直接排除掉一半候选，把复杂度从 O(n) 压到 O(log n)。两者一朴一巧，构成了查找算法的基本盘：数据无序或数据结构不支持随机访问（如链表）时用线性查找；数据有序且能随机访问（如有序数组）时用二分查找。
二分查找的全部考点集中在「边界」二字：①区间的开闭定义——[l,r]（左闭右闭）、[l,r)（左闭右开）、(l,r)（左开右开）三种写法，循环条件与 mid 收缩方式必须与区间定义自洽；②查什么——查找目标值（精确命中）、查找左边界（第一个 >= target）、查找右边界（最后一个 <= target）；③循环不变量——l、r 始终满足区间定义，是写对二分的统一心法。而二分的易错点也全是边界：mid = (l+r)/2 在大数组下整型溢出（改 l+(r-l)/2）、l = mid 而非 l = mid+1 导致死循环、while (l <= r) 与 while (l < r) 的退出语义混淆。掌握二分，本质是掌握「明确区间定义 → 守住循环不变量」这套心法，背模板只是表象。
评价
优点
- O(log n) 极速查找：二分每次排除一半，10 亿数据只需 30 次比较——这是有序数组上查找的理论最优（比较型）
- 无需额外空间：二分原地 O(1) 空间，而哈希表（O(1) 查找但 O(n) 空间）要建索引、树要存指针
- 线性查找零门槛：无序也能用、链表也能用、不支持随机访问也能用——万能的保底方案
- 适配静态数据：数据不频繁变动时，排序一次后可反复二分，摊下来极划算
缺点
- 二分强依赖有序：数据要预先排序（O(n log n)），频繁插入删除破坏有序性后二分就失效
- 强依赖随机访问：链表等不能随机访问的结构无法二分（只能 O(n) 线性查找）
- 边界极易写错：死循环、溢出、返回值含义混淆是面试最高频的 bug 源——稍不留神就
l = mid死循环或mid溢出 - 不适合动态数据：频繁插入删除的场景，有序数组维护成本 O(n)，此时应改用平衡树 / 跳表
本叶地图
- 入门 —— 线性查找 O(n)、二分查找 O(log n)、二分的前提（有序 + 随机访问）、有序数组为何能二分、二分 vs 哈希表怎么选
- 二分查找详解 —— 三种区间写法（左闭右闭 / 左闭右开 / 左开右开）、查找目标值、查找左边界、查找右边界、循环不变量
- 边界与坑 —— 死循环原因、
mid溢出、退出条件、返回值含义、写二分的统一心法 - 参考 —— 复杂度表、三种区间写法代码模板、左 / 右边界模板、易错点清单