小时候的课间，总有人喜欢玩“你心里想一个 1 到 100 的数，我来猜”。新手从 1 开始一个一个问，运气差要问 100 次；但老手第一句永远是“50”。“小了！”——好，答案在 51 到 100 之间；“大了！”——就在 1 到 49 之间。无论哪种回答，候选范围都被砍掉一半。再猜中间值，再砍一半……最多 7 次，答案必然浮出水面。这个游戏里藏着一台计算机最优雅的算法之一：二分搜索。它不排序、不遍历，只靠“每次把搜索区间减半”这一招，就能在百万、十亿条数据里闪电般定位目标。查字典翻中间页、数据库索引加速、用 git 定位首个出错提交，背后都是它的身影。本文就沿着这条“减半”之路，把二分搜索的原理、写法、坑位和进阶玩法一次讲透。

岗位关联

对 AI 从业者而言，二分搜索不仅是面试必考的算法，更是理解索引优化、日志排查、参数调优等工程实践的地基，值得花一小时彻底掌握。

目录
  1. 可视化演示
  2. 二分搜索原理
  3. 算法流程细节
  4. 复杂度剖析
  5. 经典代码变体
  6. 边界陷阱排查
  7. 高级应用拓展
  8. 工程实战指南
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示二分搜索的逐步执行过程：在有序数组中通过比较中间元素缩小搜索范围，以及与线性搜索的时间复杂度对比。

本节配有交互动效（进入视口后自动加载，约 3KB）。

二分搜索过程 搜索范围：[left, right] 中间元素：mid = (left+right)/2 命中：arr[mid] = target T(n) = O(log n) （对数时间复杂度） 每次比较将搜索范围缩小一半，适用于有序数组

二分搜索原理

课间的猜数字游戏里，老手为什么第一句总是“50”？因为“50”把 1~100 这个集合从中间劈成两半：无论答案是“大了”还是“小了”，至少有一半数字可以永远不再考虑。这一问的妙处在于——它逼着对手用一句话替你完成了“排除 49 个候选”的工作。接下来在剩下的 50 个里再取中间，继续劈……这就是整个游戏的全部秘密：每次把候选砍半。

计算机要在一堆数据里找目标，最笨的办法是从头挨个比，这叫线性查找。而二分搜索另辟蹊径：它要求数据先排好队（有序数组），然后每次只问“目标在中间元素的左边还是右边”。比如在 [1, 3, 5, 7, 9, 11, 13] 里找 9，先看中间元素 7，9 比 7 大，于是 7 和它左边的所有元素全部出局，剩下 [9, 11, 13] 继续。这种“每次缩小问题规模”的思路，在算法里叫减治法（decrease-and-conquer）——不是把问题拆成多份，而是每轮直接扔掉没希望的那一半。

用两个指针 low 和 high 框住当前候选区间，中间下标记作 mid。比较 arr[mid] 与目标 target：相等即命中；arr[mid] < target 说明目标在右半，把 low 移到 mid + 1；否则说明在左半，把 high 移到 mid - 1。如此往复，候选数量从 n 开始每轮减半：

猜数字时，“50？”这一问就是一次“mid 探测”；游戏里你记住的“范围比以前小了一半”，正是公式里那个分母 2。二分搜索的全部优雅，就藏在这个简单的除以二里。

S(k)=n2kS(k) = \frac{n}{2^k}
公式解读：第 k 次探测之后，候选元素还剩 n/2^k 个；当它小于 1 时，说明区间已被搜空。
  1. S(k) 的含义第 k 次比较结束后，仍然“可能藏着目标”的元素个数。
    S(k)S(k)
  2. n 是初始规模数组一开始有 n 个候选元素。
    nn
  3. 2^k 表示连除 k 次每探测一轮就除以 2，k 轮后共除以 2 的 k 次方。
    2k2^k
  4. 判空条件当 2^k 超过 n 时 S(k) < 1，区间为空，搜索结束。
    S(k)<1  ⟺  2k>nS(k) < 1 \iff 2^k > n

算法流程细节

玩猜数字时，高手脑子里始终挂着两个数：目前“最小可能答案”和“最大可能答案”。比如先排除了 50 及以下，又确认 75 太大，那么区间就是 51~74，下一句必是“62？”——正好是区间的中间值。低界、高界、取中点，这三步构成了每一轮的标准动作。

代码里对应三个变量：low（左指针）、high（右指针）、mid（中间下标）。一个经典问题是 mid 怎么算最稳。直接写 (low + high) / 2 在数学上没错，但在 Java/C++ 这类定长整数语言里，两个很大的整数相加可能溢出成负数，mid 瞬间飞出数组。工业界通行写法是“先量区间长度的一半，再从左边出发”。循环条件也有讲究：找“恰好相等”用 while (low <= high) 最直观；找“边界位置”常用左闭右开 while (low < high)，第 4 节会细聊。

完整的一次探测写成公式就是：

游戏里你从不怀疑区间记录会错，代码也一样——只要 low、high、mid 三个变量各司其职，区间每轮严格缩小，循环就一定会终止。所谓“写对二分”，就是把心里那笔“范围账”一丝不苟地翻译成赋值语句。

mid=low+⌊high−low2⌋\text{mid} = \text{low} + \left\lfloor \frac{\text{high} - \text{low}}{2} \right\rfloor
公式解读：用“low 加上区间长度的一半”来代替 (low+high)/2，既防溢出，语义也更直观。
  1. high - low当前区间长度，以“下标差”衡量。
    high−low\text{high} - \text{low}
  2. ⌊(high-low)/2⌋长度的一半向下取整，得到相对 low 的偏移量。
    ⌊high−low2⌋\left\lfloor \frac{\text{high} - \text{low}}{2} \right\rfloor
  3. low + 偏移在左指针基础上加上偏移量，才是真正的中间下标。
    mid=low+⌊high−low2⌋\text{mid} = \text{low} + \left\lfloor \frac{\text{high} - \text{low}}{2} \right\rfloor
  4. 更新规则arr[mid] < target 时 low = mid + 1，否则 high = mid - 1，保证 mid 被排除。
    low=mid+1 或 high=mid−1\text{low} = \text{mid} + 1 \quad \text{ 或 } \quad \text{high} = \text{mid} - 1

复杂度剖析

猜数字最迷人的地方在于：范围扩大一万倍，代价几乎不涨。1~100 最多猜 7 次；1~1000 最多 10 次；1~100 万也就 20 次。换成生活场景感受一下：线性查找像雇人挨个敲门，人越多越慢；二分则像打电话问“目标在你左边还是右边”，每问一次整张地图就缩小一半，问 20 次就能从一百万里锁定唯一坐标。

数学上，设 T(n) 是规模为 n 的数组所需的比较时间。每次二分只做一次比较和一次指针更新，都是常数时间 O(1)，剩下的问题规模减半，于是有递推关系 T(n) = T(n/2) + O(1)。把它一层层展开：T(n) = T(n/4) + 2O(1) = …… = T(1) + log₂n × O(1)，所以：

猜数字 7 次上限的来历正是 log₂100 ≈ 6.64 向上取整。你每多问一次，候选就从“几十”跳到“几”，这种爆炸性的收敛速度，是二分在数据海洋里始终屹立不倒的根本原因。

T(n)=T(n2)+O(1)  ⟹  T(n)=O(log⁡2n)T(n) = T\left(\frac{n}{2}\right) + O(1) \implies T(n) = O(\log_2 n)
公式解读：决策树的高度是 log₂n，走完整棵树就是二分最坏情况的开销。
  1. T(n)规模为 n 的问题所需的时间。
    T(n)T(n)
  2. T(n/2)一次比较后只剩一半候选，于是递归求解规模减半的子问题。
    T(n2)T\left(\frac{n}{2}\right)
  3. O(1)一次比较加上指针更新，是固定开销。
    O(1)O(1)
  4. 递推求解从 n 缩到 1 需要 log₂n 次砍半，总时间为对数级；全程只用了 low、high、mid 三个变量，空间复杂度恒为 O(1)。
    T(n)=O(log⁡2n)T(n) = O(\log_2 n)

经典代码变体

猜数字游戏其实也可以换玩法：不猜“恰好等于答案的数”，而是猜“第一个能让我获胜的位置”。比如题目变成“告诉我第一个大于等于 60 的数字是几”，规则变了，但骨架没变——还是取中间、看大小、砍一半。二分的灵魂从来不是“找相等”，而是“定位分界点”。

工程里的二分变体大致有三种：标准查找（找到目标下标就返回）、下界查找 lower_bound（返回第一个 ≥ target 的下标）、上界查找 upper_bound（返回第一个 > target 的下标）。三者唯一的区别，在于“arr[mid] == target 时往哪走”：标准查找直接返回；lower_bound 继续向左压（high = mid），因为左边可能还有相等的元素；upper_bound 继续向右压（low = mid + 1）。

以下界查找为例，收缩规则可以用分段函数表示：

游戏规则千变万化，“每次都猜中间”的解题骨架却始终如一。真实编码时，Python 的 bisect 模块、C++ 的 std::lower_bound、Java 的 Arrays.binarySearch 早就把这些变体打磨到极致——记住规律、直接用标准库，才是工程上的最优解。

{high=mid,arr[mid]≥targetlow=mid+1,arr[mid]<target\begin{cases}\text{high} = \text{mid}, & arr[\text{mid}] \ge \text{target} \\\text{low} = \text{mid} + 1, & arr[\text{mid}] < \text{target}\end{cases}
公式解读：等于 target 时不急着返回，而是保留 mid 向左压缩，循环结束后 low 恰好停在下界上。
  1. arr[mid] ≥ target 时mid 及其右边都满足条件，但左边可能还有更早的满足者，所以把 high 收到 mid。
    high=mid\text{high} = \text{mid}
  2. arr[mid] < target 时mid 处不满足条件，mid 及其左边全部排除。
    low=mid+1\text{low} = \text{mid} + 1
  3. 循环条件配合 while (low < high) 左闭右开写法，区间不断向左收敛。
    while (low<high)\text{while } (low < high)
  4. 终止与返回结束时 low == high，这个位置就是第一个 ≥ target 的下标。
    low=high\text{low} = \text{high}

边界陷阱排查

猜数字游戏里最蠢的失误是什么？每次猜“中间偏左的那个数”，对手说“大了”，你吓得把答案改小了，但下一轮又固执地猜回同一个数——这不是猜，是复读。二分代码里最经典的死循环，病根同样是“区间没有缩小”。

死循环的典型配方：写了 while (low < high)，收缩却写成 low = mid。当区间只剩下相邻两个下标时，mid = low，于是 low 原地不动，区间永远停在两个元素上，循环再也跳不出去。另一个高频事故是 (low + high) / 2 溢出——所以防溢出公式（mid = low + (high-low)/2）不是炫技，是保命。

死循环的临界状态可以用公式刻画：

写二分之前先问自己：我的区间是闭的还是半开的？收缩时 mid 有没有被排除？然后用空数组、单元素、双元素、目标在最左/最右这些“最小怪”测一轮——就像猜数字新手先拿 1~3 练习一样，能把绝大多数边界 bug 扼杀在摇篮里。

high=low+1  ⇒  mid=⌊low+high2⌋=lowhigh = low + 1 \;\Rightarrow\; mid = \left\lfloor \frac{low + high}{2} \right\rfloor = low
公式解读：区间只剩两个元素时，下取整的 mid 总是指向左端点；此时若收缩规则是 low = mid，新区间长度不变，循环永远走不完。
  1. high = low + 1区间收缩到只剩相邻两个下标的临界状态。
    high=low+1high = low + 1
  2. mid = low下取整让中间下标恰好等于左端点 low。
    ⌊low+high2⌋=low\left\lfloor \frac{low+high}{2} \right\rfloor = low
  3. low = mid 的后果low 没变，新区间仍是 [low, high]，长度不变，死循环。
    low=mid⇒区间长度不变\text{low} = \text{mid} \Rightarrow \text{区间长度不变}

高级应用拓展

游戏升级了：出题人把 1~100 的卡片排成环，再从某个位置剪开、重新接成一条“有折痕”的序列，比如 [50, 60, 70, 80, 90, 10, 20, 30]。这时序列不再完全有序，但有一个重要特点：剪开的位置把整条序列分成了两段，每段内部依然有序。聪明的你依然可以快速锁定目标。

这就是旋转数组搜索。关键观察是：无论从哪刀切下去，取中间位置后，左半段和右半段至少有一段是完全有序的。通过比较 arr[mid] 与 arr[high] 就能判断哪半段有序：若 arr[mid] < arr[high]，右半段有序；否则左半段有序。再判断目标是否落在这段有序区里，就能决定舍弃左半还是右半。整体复杂度依然是 O(log n)。

更广泛的进阶玩法是“二分答案”：把“求最优解”转化成“判断某个候选解 x 是否可行”。判定规则概括为：

旋转数组像被剪断又接上的卡片串，二分靠着“总有一段有序”的线索照样找出目标；二分答案则像是把游戏从“猜数字”升级成“猜边界”——出题人只回答“行不行”，你依然能靠砍半快速逼近真相。变的只有规则，不变的是每次砍掉一半的智慧。

f(x)={true,x 可行false,x 不可行且 f 单调，就在值域上二分逼近f(x) = \begin{cases}true, & x \text{ 可行} \\false, & x \text{ 不可行}\end{cases}\quad \text{且 } f \text{ 单调，就在值域上二分逼近}
公式解读：直接求最优解很难时，先把“可行性判定”写成单调函数 f(x)，再用二分反复试探，逼近答案。
  1. f(x)判定“候选解 x 是否可行”的布尔函数，比如“预算 x 能不能让活动办完”。
    f(x)f(x)
  2. 单调性要求x 增大时 f 只从 false 变 true（或反过来），二分才有方向可循。
    单调性\text{单调性}
  3. 二分逼近每次取值域中点 m，根据 f(m) 是 true 还是 false，砍掉一半值域。
    若 f(m)=true，答案留在可行侧\text{若 } f(m) = true \text{，答案留在可行侧}

工程实战指南

熟练了猜数字之后你会发现，生活处处是二分：查词典先翻到中间页，找书先在书架中段摸一下方向，排查“网怎么又慢了”先判断是路由器还是光猫……工程世界里更是如此，二分早已内化进无数工具。

真实开发的第一条准则是：能调标准库就别自己写。Python 的 bisect 模块、C++ 的 std::lower_bound、Java 的 Arrays.binarySearch，边界处理都被锤炼了数十年。第二条准则是先评估规模：如果数组无序、而且总共只查一次，直接线性扫描可能更快——因为排序本身是 O(n log n)，比一次 O(n) 的遍历贵得多。二分查找单个有序数组的最坏比较次数有上界：

最后别忘了，最实用的二分工具其实藏在 git 里——git bisect 在提交历史这条“有序时间轴”上二分，自动定位“从哪一个 commit 开始坏掉”，简直就是猜数字游戏的版本管理版。掌握二分，你就握住了一把从数据检索到工程排障都通用的钥匙。

比较次数≤⌈log⁡2(n+1)⌉\text{比较次数} \le \lceil \log_2(n+1) \rceil
公式解读：n 个有序元素，二分最多比较 ⌈log₂(n+1)⌉ 次；百万级数据约 20 次。
  1. n有序数组的元素个数，也就是二分面对的候选总数。
    nn
  2. ⌈log₂(n+1)⌉向上取整的对数，是最坏情况下的比较次数上界。
    ⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil
  3. 决策标准当查询次数 m 超过这个上界时，排序+二分的总开销开始优于多次线性扫描。
    m>⌈log⁡2(n+1)⌉m > \lceil \log_2(n+1) \rceil

AI 应用场景

数据库索引的节点内二分

阶段：数据存储与检索

解决的问题：全表扫描是 O(n)，在亿级数据下不可用。B+ 树索引把数据组织成多层节点，每个节点内有序存储键值，查询时用二分定位键的位置，把磁盘 I/O 次数从 O(n) 降到 O(log n)——这正是“猜数字每次砍半”在存储引擎里的化身。

具体案例：某电商订单表 5000 万行，无索引时按订单号查询需全表扫描约 5 秒；加上 B+ 树索引后查询降到毫秒级，背后正是每个节点内的二分定位。数据库工程师优化慢查询时，explain 看到索引命中，靠的就是这层二分加速。

git bisect 定位回归 bug

阶段：工程调试与排障

解决的问题：新功能上线后出现性能回归，几十个 commit 不知道是哪个引入的。git bisect 在提交历史这个“有序序列”上二分，每次 checkout 中间提交并测试，log₂64 = 6 轮就能定位首个坏 commit，而不是逐个回退试错。

具体案例：某团队发现线上接口延迟从 50ms 涨到 500ms，用 git bisect 标记“已知坏”的最新 commit 和 32 个 commit 前的“已知好”提交，二分 6 轮后锁定“引入 N+1 查询”的那次提交，10 分钟完成定位。

广告出价中的二分答案

阶段：算法策略调参与优化

解决的问题：广告系统里“给定预算，求最大可承受的单次出价，使预算恰好花完”这类单调判定问题，直接求解很困难。把“出价 x 是否可行”写成单调函数 f(x)，在出价值域上二分，O(log 值域) 次模拟即可逼近最优解，替代了原来的穷举网格搜索。

具体案例：推荐广告团队做预算平滑，需要为每个流量找到“兜底出价”，他们在 [0, 最高限价] 区间反复模拟消耗，十几轮二分后就得到满足预算约束的最高出价，上线后预算消耗误差从 8% 降到 1% 以内。

Python 演示

python48 行
"""二分搜索三连: 标准查找, 边界查找, 二分答案."""  def binary_search(arr, target):    """标准二分: 闭区间 [low, high], 返回目标下标, 不存在时返回 -1."""    low, high = 0, len(arr) - 1    while low <= high:        mid = low + (high - low) // 2        if arr[mid] == target:            return mid        if arr[mid] < target:            low = mid + 1        else:            high = mid - 1    return -1  def lower_bound(arr, target):    """左边界二分: 左闭右开 [low, high), 返回第一个 >= target 的下标."""    low, high = 0, len(arr)    while low < high:        mid = low + (high - low) // 2        if arr[mid] < target:            low = mid + 1        else:            high = mid    return low  def sqrt_int(x):    """二分答案: 在值域 [0, x] 上二分, 返回根号 x 的整数部分."""    low, high = 0, x    while low <= high:        mid = low + (high - low) // 2        if mid * mid <= x:            low = mid + 1        else:            high = mid - 1    return high  if __name__ == "__main__":    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]    for t in (7, 8, 19):        print("binary_search({}) = {}".format(t, binary_search(arr, t)))    print("lower_bound(9) =", lower_bound(arr, 9))    print("sqrt_int(16) =", sqrt_int(16))    print("sqrt_int(17) =", sqrt_int(17))
目的：一份可直接运行的 Python 脚本，演示标准二分、下界二分与二分答案三种最常用形态，覆盖正文全部核心知识。
  1. mid = low + (high - low) // 2先算区间一半再加到 low 上，杜绝 low+high 溢出。
  2. while low <= high闭区间写法，适合“找相等元素”的标准查找。
  3. low = mid + 1` 与 `high = mid - 1排除 mid 本身，保证区间严格缩小。
  4. low, high = 0, len(arr)左闭右开区间，右边多让出一个位置，统一语义。
  5. high = mid保留 mid 向左压缩，配合左闭右开防止死循环。
  6. mid * mid <= x把“会不会超过 x”当成单调判定函数，典型的二分答案。
  7. if __name__ == "__main__":让脚本既可以 import 也可以直接运行做演示。

常见误区

误区我之前听说二分前提是有序，所以我每次都要先写排序，甚至要求数组不能有重复元素，否则就不敢用二分。

正解二分的本质是“存在一个单调的判定条件，能把候选一分为二”。完全有序只是最常见的情形。重复元素完全可以二分——lower_bound/upper_bound 正是为重复而生；旋转数组（两段各自有序）也能二分；甚至单调函数的值域也可以二分。只盯着“严格升序”，会错过二分更大的用武之地。

为何常见：教科书与入门教程几乎都用“有序数组查找元素”作为第一个例子，导致学习者把“示例”误当成了“前提”。

误区while low < high 和 while low <= high 我经常混着写，反正数据不大时结果都一样，跑通就行。

正解边界条件不一致在“目标不存在”“目标在最左/最右”“区间长度为 1”时立刻翻车——轻则返回错误下标，重则死循环。二分必须以“循环不变式”为准绳：先定清楚区间是闭还是半开，再定收缩规则，最后用长度为 0、1、2 的最小用例验证。

为何常见：二分代码短，看起来“随便写写就过了”，普通测试数据又掩盖了边界差异，只有极端输入才会暴露。

误区两个式子数学上一样，我写短的就行，根本不会出问题。

正解数学上等价，但在 Java/C++ 等定长整数语言里，low + high 可能超过 int 最大值变成负数，mid 立刻越界。这在超大数组、内存地址计算时是真实事故。Python 的 int 无限大所以无感，但好习惯要养在代码里。

为何常见：Python 的大整数让溢出“隐形”，很多人在 Python 里写多了，就默认全世界都不会溢出。

误区二分就是查数组里有没有 target，找到了就完事，其他场景用不上。

正解二分的完整能力是“在单调结构上定位分界点”。找相等元素只是它的子集。找左边界/右边界、找插入位置、旋转数组找最值、函数值域上二分答案、浮点数逼近，都是同一套思想。面试与工程里 80% 的二分题，考的都不是“找相等”。

为何常见：入门示例全是“找相等元素”，缺少对“分界点定位”这一抽象本质的提炼，导致知识迁移失败。

面试题

Q1. 关于二分搜索的使用前提，下列说法正确的是？

单选题 · easy

  • A.数组必须完全严格升序且无重复
  • B.存在单调判定条件，可将候选区间一分为二← 正确答案
  • C.数组长度必须是 2 的整数次幂
  • D.数组必须是整型数组

答案：B。二分搜索的本质是利用单调性逐步缩小搜索区间。“有序”是最常见的单调形式，但重复元素、旋转数组甚至单调函数值域都可以二分，因此 B 最准确；A 过于苛刻，C 与 D 没有根据。

Q2. 1~100 的猜数字游戏，用“每次猜中间”的策略，最坏情况需要猜几次？

单选题 · easy

  • A.6 次
  • B.7 次← 正确答案
  • C.10 次
  • D.50 次

答案：B。每次猜测把候选区间砍半，n=100 时最多 ⌈log₂(100+1)⌉ = 7 次。这正是二分最坏情况下比较次数上界的日常体现。

Q3. 在闭区间写法的标准二分中，若 arr[mid] < target，正确的收缩是？

单选题 · mid

  • A.low = mid
  • B.low = mid + 1← 正确答案
  • C.high = mid
  • D.high = mid - 1

答案：B。arr[mid] < target 说明目标只可能在 mid 右侧，mid 本身已排除，应令 low = mid + 1。若写成 low = mid，当区间只剩两个元素时 mid 恒等于 low，会造成死循环。

Q4. mid = low + (high - low) // 2 相比 (low + high) // 2 的主要优势是？

单选题 · mid

  • A.计算速度更快
  • B.结果总是整数
  • C.避免 low + high 整数溢出← 正确答案
  • D.能处理无序数组

答案：C。在 Java/C++ 等定长整数语言中，low 与 high 都很大时 low + high 可能超过 int 上限变为负数，导致 mid 越界。先算区间长度的一半再从 low 出发，可彻底规避该问题。

Q5. 二分搜索的时间复杂度和空间复杂度分别是？

单选题 · mid

  • A.O(n)、O(n)
  • B.O(log n)、O(1)← 正确答案
  • C.O(log n)、O(log n)
  • D.O(n)、O(1)

答案：B。每次比较后问题规模减半，递推式 T(n)=T(n/2)+O(1) 解得 O(log n)；整个过程只维护 low、high、mid 三个变量，空间为 O(1)。

Q6. 在有序数组 [0, 1, 2, 3, 4, 5, 6, 7] 中用二分查找 5，第一次检查的下标是？

单选题 · mid

  • A.3← 正确答案
  • B.4
  • C.5
  • D.7

答案：A。初始 low=0、high=7，mid = 0 + (7-0)//2 = 3，所以第一次比较 arr[3] = 3 < 5，然后 low 变成 4，第二次才检查下标 5。第一次一定是中间下标 3。

Q7. 在旋转数组 [4, 5, 6, 7, 0, 1, 2] 中找最小值，常用判断“哪半段有序”的比较对象是？

单选题 · hard

  • A.arr[mid] 与 arr[low]
  • B.arr[mid] 与 arr[high]← 正确答案
  • C.arr[0] 与 arr[high]
  • D.arr[mid] 与 arr[0]

答案：B。旋转数组任意切一刀，左半或右半至少一边有序。比较 arr[mid] 与 arr[high]：若 arr[mid] < arr[high]，右半段严格递增，最小值在左半（含 mid）；否则最小值在右半。B 是最常用的判定方式。

Q8. 关于二分搜索，下列说法正确的有？

多选题 · mid

  • A.空间复杂度为 O(1)← 正确答案
  • B.要求数据支持随机访问（如数组），链表上直接二分会退化← 正确答案
  • C.可以用于查找第一个不小于目标值的位置← 正确答案
  • D.数组必须严格递增且无重复才可用

答案：ABC。二分靠下标算术移动，链表无法高效取中点，随机访问是前提；边界查找专门处理重复值场景，A、B、C 都对。D 把“严格有序”当硬前提是常见误解，重复元素完全可用。

Q9. 以下哪些写法组合可能导致二分死循环？

多选题 · hard

  • A.区间 [low, high)，收缩为 low = mid, high = mid← 正确答案
  • B.区间 [low, high]，收缩为 low = mid + 1, high = mid - 1
  • C.区间 [low, high)，收缩为 low = mid + 1, high = mid
  • D.区间 [low, high]，收缩为 low = mid, high = mid - 1← 正确答案

答案：AD。A 与 D 的收缩规则都可能让 mid 留在新区间内且区间长度不减少，当区间只剩相邻两个元素时 mid 恒等于某个边界，于是死循环。B 与 C 每次都至少排除 mid 一个元素，区间严格缩小，必然终止。

Q10. 二分搜索适用于下列哪些情形？

多选题 · easy

  • A.在有序数组中判断元素是否存在← 正确答案
  • B.查找第一个大于等于目标值的位置← 正确答案
  • C.值域上的单调判定问题（二分答案）← 正确答案
  • D.在完全无序的数组中找最大值

答案：ABC。A 是标准用法，B 是 lower_bound，C 是二分答案法，三者都是“在单调结构上定位分界点”的体现。D 无序且无单调性，二分无从下手，线性扫描才是正解。