（d2）有序向量：二分查找

官官方信息技术老师·10 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ （d2）有序向量：二分查找信息技术（d2）有序向量：二分查找概述

有序向量二分查找边界细节算法分析

（d2）有序向量：二分查找

掌握三种区间写法的边界细节，看清折半背后的陷阱

按空格/→ 演示下一步

1 / 10 页

全部页面点击任意一页，跳回舞台从这页播放

有序向量二分查找边界细节算法分析

（d2）有序向量：二分查找

掌握三种区间写法的边界细节，看清折半背后的陷阱

1第 1 页 · （d2）有序向量：二分查找

概述

查英汉字典时，你不会从 a 一路翻到 z——而是直接翻到中间，按"偏前/偏后"判断，每次砍掉一半。这就是二分查找的核心思路。

有序性前提

向量已按关键字排序；无序则无法判方向，二分失效

折半策略

取中点比较，每次将候选区间长度减半

对数复杂度

比较次数 ≤ ⌈log₂ n⌉，百万规模仅需 ~20 次

失败判定

lo > hi 时区间为空，确认目标不在集合中

典型应用

字典查询、版本号定位、数据库索引、有序统计

猜数字游戏（1~100）对应 →二分查找

每次猜中间数，按偏大/偏小砍掉一半，步数恰为 log₂n

T(n) = T(n/2) + O(1) = O(\log n)

2第 2 页 · 概述

接口

二分查找快得惊人——但前提是输入「对得上」、接口「讲得清」。这一页把接口摊开，看清它承诺什么、不承诺什么。

接口签名

参数:目标元素 e、范围 [lo, hi);返回:秩 rank

单调性前提

[lo, hi) 内元素必须单调非降,否则结果无意义

返回语义

命中返回 e 的秩;未命中约定返回 -1

两种变体

精确查找返命中秩;插入位查找返首个 >= e 的秩

适用范围

仅适用于支持 O(1) 随机访问的向量,链表不行

翻英汉词典查单词对应 →二分查找接口

字典按字母排序=单调性;翻到中部=折半;查到词条即返回秩

3第 3 页 · 接口

语义

我们已经知道二分查找的接口形态，但它到底在'找'什么？返回位置又意味着什么？这一页把语义钉死——否则后续看代码会一直被细节困扰。

返回的是秩(rank)

search(e) 返回 e 在有序向量中的秩，即 ≤ e 的元素个数 i，范围 [lo, hi]

失败也返回秩

未命中时返回 e 若插入应保持有序的位置，是合法秩而非 -1

版本变体

按 ≤e / <e(以及 ≥e / >e) 定义不同边界，语义各异；选错即破坏正确性

典型应用

范围计数 rank(b)−rank(a−1)、前驱后继、去重皆依赖秩的语义

查字典找某字对应 →二分查找的秩

字典告诉你'应在第几页'，即使未找到也给出插入位置

r = \operatorname{search}(e) = \max\{i \in [lo, hi] : V[i-1] \leq e\}

4第 4 页 · 语义

原理

前几页我们看了二分查找的「是什么」（概述）、「怎么用」（接口）、「返回什么」（语义）。这页钻进机制：凭什么它比顺序查找快这么多？核心只有四个字——折半淘汰。

有序性前提

数组必须按关键码升序排列，否则折半判断会把目标砍到错误的那一半

折半淘汰

每次取中点与目标比较，根据大小关系将候选区间一刀切掉一半

对数复杂度

百万级数据最多 20 次比较就能定位；n 越大，相对顺序查找优势越悬殊

边界约定

区间开闭（[lo,hi) 还是 [lo,hi]）决定了 mid 公式与循环终止条件

查英汉词典找生词对应 →二分查找

不会从第一页翻到最后一页——先翻中间，根据字母序决定往前半还是后半，每次砍掉一半页码

T(n) = T\!\left(\tfrac{n}{2}\right) + O(1) \Rightarrow T(n) = O(\log n)

5第 5 页 · 原理

实现

原理说每次砍一半范围。但落到代码上全是细节：循环用 lo<=hi 还是 lo<hi？中点怎么算不溢出？找不到返回什么？这页就拆这些坑。

区间约定

选闭区间 [lo,hi] 还是半开 [lo,hi)，决定后续所有代码写法

中点防溢出

用 lo+(hi-lo)/2 替 (lo+hi)/2，大数组避免整数溢出

循环与边界更新

闭区间配 lo<=hi、hi=mid-1；半开配 lo<hi、hi=mid

返回值约定

找到返回下标；找不到可返 -1 或插入位置

尺和米两种长度单位对应 →闭区间和半开区间两种写法

两种都对，但混用就出错；选一个就一路用到底

mid = lo + \frac{hi - lo}{2}

6第 6 页 · 实现

实例

翻英语词典查 'binary'——你不会从 A 翻到 Z，而是直接翻到字典中段，看首字母落在哪个字母区间，再决定往前翻还是往后翻。这就是二分查找的典型场景。下面看几个具体例子。

标准命中

目标恰为当前中点 A[mid]，直接命中返回

偏向命中

目标较小走左半区间，较大走右半区间

查无此数

区间缩到 lo > hi 仍未命中，查找失败

重复定位

在重复元素中定位首个/末个——lower_bound 与 upper_bound

插入点查找

返回目标应插入的位置，即保持有序的最小下标

翻字典查单词对应 →有序向量的二分查找

每次看当前页首字母落到哪个字母段，再决定向前或向后翻——区间每步折半

7第 7 页 · 实例

查找长度

上一节我们用二分查找命中了目标。但每次成功需要比较几次？为什么有时快有时慢？这就要引入「查找长度」——度量查找效率的统一标尺。

定义

一次查找过程中，关键码（key）的比较次数

取决于目标位置

同一算法，查找不同元素所用比较次数可能不同

成功查找的长度

等于判定树中命中节点的深度 + 1

失败查找的长度

等于判定树中外部节点（哨兵位）的深度 + 1

猜数字游戏（1~100）对应 →二分查找的查找长度

每猜一次、对方答一次「大了/小了」就是一次比较；总共猜几次就是查找长度

\text{查找长度}(v)\;=\;\text{depth}(v)\;+\;1

8第 8 页 · 查找长度

本节要点

✓O(log n) 源于决策树高度,不是循环次数本身
✓lo/hi/mid 的分界语义即不变式,代码只是表达
✓n=0、1、2 的退化情形是验证正确性的试金石
✓失败查找总比成功多一层比较,体现在 ASL 公式上

延伸主题：插值查找与三分查找的适用边界二分与二分查找树的等价与差异

9第 9 页 · 本节要点

课后思考

先自己想想，再看参考答案。三题分别对应核心、应用和迁移。

1二分查找能达到 O(log n) 的关键前提是什么？它在哪些场景下会被破坏？

参考答案关键是顺序存储加有序性，可以 O(1) 随机访问下标。破坏场景：链表无法随机访问，频繁插入删除的动态场景也不再适用。

2如果有序向量里存在重复元素，如何找到目标值第一次出现的下标？

参考答案找到后不立即返回，继续向左二分直到左邻不等于目标或越界。经典做法是用 lower_bound 思路收缩右边界。

3把有序向量的数组换成单向链表，二分查找还能保持 O(log n) 吗？为什么？

参考答案不能。链表访问中点需要 O(n) 遍历，整体退化为 O(n)。二分的高效建立在顺序存储的 O(1) 随机访问上。

10第 10 页 · 课后思考