入门：线性 O(n) 与二分 O(log n) 的分水岭
基于通用算法概念 · 核于 2026-07
速查
- 线性查找（Linear Search）：从头到尾顺序扫描逐个比较，O(n)——无序也能用，链表、文件流、不支持随机访问的结构都能用，是查找的「保底方案」。
- 二分查找（Binary Search）：每次比较中点后靠有序性排除一半候选，O(log n)——10 亿数据只需约 30 次比较，是有序数组上查找的理论最优。
- 二分的两个硬前提：①数据有序（升序或降序）；②结构支持随机访问（数组可以，链表不行）——缺一个都不能二分。
- 有序数组为何能二分：比较
a[mid]与target后，由于有序，可以确定另一半不可能含 target，于是搜索区间每次缩小一半，至多log₂n次就收敛。 - 复杂度对照：线性查找最好 O(1)/最坏 O(n)/平均 O(n)；二分查找最好 O(1)/最坏 O(log n)/平均 O(log n)——n 越大二分优势越碾压。
- 二分 vs 哈希表：哈希表查找 O(1) 比二分 O(log n) 更快，但需要 O(n) 额外空间建索引、有哈希冲突；二分原地 O(1) 空间、无冲突、适合静态有序数据。
- 二分 vs 树 / 跳表：二分适合静态有序数组（查询多、改动少）；若需频繁插入删除维持有序，改用平衡树（O(log n) 增删查）或跳表。
- 二分不是只能查「相等」：还能查「第一个
>= target」（左边界/下界）、「最后一个<= target」（右边界/上界）——这是二分的真正威力。 - 二分的边界才是难点：区间开闭（
[l,r]/[l,r)/(l,r)）、while条件、mid收缩、返回值含义——稍错就死循环或漏解。 mid防溢出：写mid = l + (r - l) / 2（或l + ((r - l) >> 1)），而不是(l + r) / 2——后者在l+r超过整型上限时溢出。- 二分的思想外延：二分的不只是「下标」，还可以二分「答案」（二分答案）、二分「实数」（求根、求极值的实数二分）——前提是有单调性。
- 何时线性查找更合适：数据无序且只需查一次（排序的 O(n log n) 比线性 O(n) 还贵）、数据不支持随机访问（链表）、n 很小（常数因子下线性可能更快）。
- 进阶顺序：二分查找详解（三种区间写法 + 三种边界） → 边界与坑（死循环/溢出/退出条件） → 参考（模板与易错速查）。
一、线性查找：朴素但万能
线性查找就是「从头扫到尾，找到就返回」：
// 线性查找：返回 target 的下标，找不到返回 -1
function linearSearch(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i; // 命中
}
return -1;
}它不要求任何前提——数组无序、是链表、是文件流，都能逐个比较。复杂度上：最好 O(1)（第一个就是）、最坏 O(n)（在末尾或不存在）、平均 O(n)。它的价值正在于「万能」：当你不确定数据是否有序、或数据结构不支持随机访问时，线性查找永远能用。这也是为什么大多数语言的 indexOf / find 内部就是线性查找——它没有前提。
线性查找唯一的「优化」是提前终止：找到目标就 return，不必扫完。但要判断「不存在」仍需扫完整个数组，所以最坏仍是 O(n)。
二、二分查找：有序数组上的 O(log n)
二分查找的核心思想是「每次排除一半」。它建立在两个硬前提上：
- 数据有序：升序（或降序），这样比较中点后能确定 target 在左半还是右半。
- 随机访问：能在 O(1) 取到任意下标的元素——数组可以，链表不行。
有了这两个前提，二分的过程是：
// 二分查找（左闭右闭写法）：返回 target 下标，找不到返回 -1
function binarySearch(nums, target) {
let l = 0, r = nums.length - 1; // 闭区间 [l, r]
while (l <= r) { // 区间非空就继续
const mid = l + ((r - l) >> 1); // 防溢出的 mid
if (nums[mid] === target) return mid; // 命中
nums[mid] < target ? (l = mid + 1) : (r = mid - 1); // 排除一半
}
return -1;
}- 为什么是 O(log n)：每次循环区间长度减半，n → n/2 → n/4 → … → 1，至多
⌈log₂n⌉ + 1次比较就收敛。10 亿（约 2³⁰）数据只需约 31 次比较。 - 为什么对：有序性保证「
a[mid] < target时左半（含 mid）全部小于 target，可整体排除」「a[mid] > target时右半同理」——每步排除的恰好是不可能含答案的那一半，不漏解。
二分的真正难点：边界
上面的「精确查找」只是二分的最简单用法。二分的真正威力（和难点）在于：
- 区间开闭：
[l,r]、[l,r)、(l,r)三种写法，while条件和l/r怎么收缩都不同——必须自洽，否则死循环或漏解。 - 查什么：不只是查「相等」，还能查「第一个
>= target」（左边界）、「最后一个<= target」（右边界）。 mid溢出：(l+r)/2在l+r超过整型上限时溢出，必须改l+(r-l)/2。
三、有序数组为何能二分：每次排除一半
二分的正确性完全来自「有序 ⇒ 单调性」。以升序数组 a[] 为例，比较 a[mid] 与 target：
- 若
a[mid] < target：由于升序，a[l..mid]都<= a[mid] < target，左半（含 mid）整体排除，l = mid + 1。 - 若
a[mid] > target：由于升序，a[mid..r]都>= a[mid] > target，右半（含 mid）整体排除，r = mid - 1。 - 若
a[mid] === target：命中。
关键在于「排除的一半确定不含答案」——这保证了不漏解。而每次区间恰好减半，保证了 O(log n)。没有有序性这一切都不成立：无序数组里 a[mid] < target 既不能说明左半都小、也不能说明右半都大，无法排除任何一半，只能退回线性扫描。
一句话：有序 ⇒ 单调 ⇒ 每次能确定地排除一半 ⇒ O(log n)。这是二分查找的物理根基，类比数组「连续内存 ⇒ O(1) 随机访问」的地位。
四、二分 vs 哈希表：静态数据 vs 动态数据
二分查找 O(log n) 和哈希表 O(1) 哪个更好？要看场景：
| 维度 | 二分查找 | 哈希表 |
|---|---|---|
| 查找复杂度 | O(log n) | O(1)（平均） |
| 额外空间 | O(1)（原地） | O(n)（建索引） |
| 数据要求 | 有序 + 随机访问 | 无（需可哈希） |
| 是否有冲突 | 无 | 有（哈希冲突） |
| 适合场景 | 静态有序数据、查询密集 | 动态数据、频繁增删查 |
- 哈希表更快但有代价：O(1) 查找的代价是 O(n) 额外空间和哈希冲突的最坏退化。二分原地 O(1) 空间、无冲突，在内存敏感或数据天然有序时更优。
- 静态 vs 动态：数据建好就不怎么变（如字典、配置表），排序一次后反复二分，摊下来极划算；数据频繁增删，有序数组维护成本 O(n)（插入要搬移），此时哈希表或平衡树更合适。
- 范围查询：二分天然支持「找第一个
>= target」「最后一个<= target」这类范围查询，哈希表做不了（只能精确匹配）。
选型口诀：「静态有序、查询密集、要范围查询 → 二分；动态数据、频繁增删、只精确匹配 → 哈希表」。
下一步
理解了线性 O(n) 与二分 O(log n) 的分水岭后，下一步是攻克二分的真正难点——三种区间写法（左闭右闭 / 左闭右开 / 左开右开）与三种查找目标（目标值 / 左边界 / 右边界），见二分查找详解。