Olverae Assets

1 先玩一局：1–100，你几次能猜到我心里的数？

规则：我心里有个 1–100 的数，你来猜，我只回答"大了 / 小了"。最省的猜法不是从 1 数起，而是每次猜区间正中间——一猜就砍掉一半。下面把这套玩法搬到一个有序数组上：点「下一步」，看三根指针 lo / mid / hi 怎么把范围一刀刀砍到只剩目标。

动手：在有序数组里找一个数

目标

试试：

点「下一步」开始。区间 = 整个数组。

比较次数 0 区间还剩 15 个理论上限 ⌈log₂15⌉ = 4 次

对应代码（每步高亮当前行）

int bsearch(int a[], int n, int target) {    int lo = 0, hi = n - 1;    while (lo <= hi) {        int mid = lo + (hi - lo) / 2;        if (a[mid] == target) return mid;        else if (a[mid] < target) lo = mid + 1;        else hi = mid - 1;    }    return -1; // 没找到}
        

你刚用的就是二分查找：在已经排好序的数组里，每次看中间那个，比一下就砍掉一半范围。lo / hi 框住"还可能藏着目标的区间"，mid 是中点。

唯一前提：数据必须有序——"大了 / 小了"只有在有序时才成立；无序数组用二分会漏掉明明存在的元素。

2 凭什么这么快：每比一次，砍掉一半

回到上面的演示——盯着那个「比较次数」：15 个元素最多 4 次就到底，因为每比一次候选数量就减半（15 → 7 → 3 → 1）。这就是 O(log n) 的含义。

每多允许一次比较，能搞定的规模就翻一倍。所以 10 亿 个有序数，二分也只要约 30 次比较就能定位——而从头线性扫最坏要 10 亿次。

查找方式	时间（最坏）	是否需有序	n=10⁶ 大约比较次数
线性查找 linear	O(n)	否	1,000,000
二分查找 binary	O(log n)	是	20

代价就是那个前提：得先有序。所以「只查一次」用线性 O(n) 就够；「反复查很多次」才值得先花 O(n log n) 排好序、之后每次 O(log n) 二分。

3 三个一写就翻车的坑（点一下看）

二分代码就十行，却是出了名的难写对——这三个坑几乎人人踩过。点卡片，下面控制台模拟运行结果。把这一节看懂，胜过背"核心要点"。

① mid 用了 (lo+hi)/2

数组很大时 lo+hi 溢出 int → mid 变负 → 越界读

② 在未排序数组上二分

元素明明在数组里，二分却返回 -1（没找到）

③ 更新写成 lo = mid

区间不缩小 → while 永远不停 → 死循环

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

4 自测

用上面那个 15 元素数组（2 5 8 12 16 23 38 56 72 73 88 91 94 97 99）想一遍，再点选项对答案。

去做例题：二分查找 · 返回下标 / 插入位置

去做例题

读完这节，你应该明白：

二分查找＝在有序数组里每次砍一半。三根指针 lo/hi 框住"还可能藏着目标的区间"，mid 是中点；比一次就丢掉一半，所以是 O(log n)。三件保命的事：必须有序、mid=lo+(hi-lo)/2 防溢出、更新用 mid±1 保证区间一定缩小（否则死循环）。把"找下标"换成"找第一个 ≥ target 的位置"，就是 lower_bound——后面学 BST 时，你会发现 BST 查找本质就是把这套二分长在了树上 ↓