想象你在和朋友玩一个游戏：朋友在 1 到 100 之间想了一个数，你每次猜一个数，他告诉你“大了”还是“小了”。你会怎么猜？如果从 1 开始挨个试，平均要猜 50 次；但如果你每次都报中间的数——先报 50，说“大了”就报 25，说“小了”就报 75——最多 7 次必中。这个“每次砍半”的策略，就是二分查找的灵魂。 计算机在一亿个有序数字里找一个目标，用的正是同一招：每次看中间那个数，“大了”就往左半找，“小了”就往右半找，一亿个数字也只需要约 27 次比较。但事情没这么简单——面试官最爱考的，不是你会不会这个思想，而是你能不能把“中间值怎么算”“左右边界怎么挪”“什么时候停”这几件事写得滴水不漏。无数人在 left 和 right 的更新上翻车，写出死循环或越界访问。 这篇文章会带着你从猜数字游戏的直觉出发，讲透二分查找的核心思想、前提条件、两种区间写法、四大查找变体、插入位置、易错边界，以及旋转数组等实战变形。学完之后，你会像高手一样，先想清楚“区间到底怎么定义”，再动笔写循环，从此不再被边界条件卡住。

岗位关联

二分查找是算法面试的“送分题”也是“送命题”。掌握它，意味着你能在 O(log n) 时间内解决海量有序数据的检索问题，这是数据库索引、AI 工程和系统设计中高频复用的基本功，也是面试官考察候选人工程严谨性的经典试金石。

目录
  1. 可视化演示
  2. 核心思想：折半砍区间
  3. 应用前提：有序可访问可比
  4. 区间写法：左闭右闭与左闭右开
  5. 查找变体：第一个与最后一个
  6. 插入位置：lower_bound 与 upper_bound
  7. 易错边界：溢出与死循环
  8. 实战应用：旋转数组与工程落地
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

分步演示二分查找在有序数组中的搜索过程，展示L、R、M指针移动和区间缩窄，对比线性搜索的步骤数差异。

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

二分查找搜索过程 紫色M为中间指针，绿色L为左边界，粉色R为右边界 mid = ⌊(L + R) / 2⌋ 点击下一步观察区间缩窄过程

核心思想：折半砍区间

猜数字游戏里，你每次报中间数，朋友的“大了”或“小了”就像一个判断器，帮你把候选范围直接截掉一半。100 个数猜 7 次，是因为 2 的 7 次方是 128，刚好覆盖 100。这个“每次砍半”的节奏感，就是二分查找的心跳。

现在把游戏移植到数组里。假设有一个有序数组 [1, 3, 5, 7, 9, 11, 13, 15]，目标值是 9。你不需要从头扫到尾，只需要维护两个“指针”——左边界 left 和右边界 right，它们圈定了当前候选区。先取中间位置 mid，把 arr[mid] 和 target 比一比：比 target 小，说明目标在右半边，于是把 left 挪到 mid 后面一位；比 target 大，说明目标在左半边，把 right 挪到 mid 前面一位。每比一次，候选区缩一半。

这个过程的效率可以用一个递推式描述：在 n 个元素里查找需要 T(n) 次比较，每轮只做常数次操作，然后问题规模减半。

这就像猜数字游戏里“最多 7 次猜中 100 以内数字”的数学保证。面试时，当你分析完这个问题并说出“每次排除一半，所以是对数复杂度”，面试官就知道你已经抓住了二分查找的灵魂：不是“找得快”，而是“砍得准”。

T(n)=T(n2)+O(1),T(n)=O(log⁡n)T(n) = T\left(\frac{n}{2}\right) + O(1), \qquad T(n) = O(\log n)
这个公式告诉你：查找时间随数据规模呈对数增长。数据翻一倍，只多一次比较。
  1. 问题规模减半每轮比较后，候选区间从 n 缩小到 n/2，所以 T(n) 依赖 T(n/2)
    T(n)=T(n2)+O(1)T(n) = T\left(\frac{n}{2}\right) + O(1)
  2. 常数时间操作一次取中值、一次比较、一次指针移动，都是常数开销
    O(1)O(1)
  3. 递推展开连续减半 k 次后规模变成 1，此时 2 的 k 次方等于 n
    2k=n  ⟹  k=log⁡2n2^k = n \implies k = \log_2 n
  4. 对数结论所以最多比较约 log2(n) 次，一百万数据只需 20 次
    T(n)=O(log⁡n)T(n) = O(\log n)

应用前提：有序可访问可比

猜数字游戏有一个隐藏前提：数字范围必须单调有序。如果朋友想的是“1 到 100 里按某种乱序排列的第 7 个数”，你说 50，他无论说“大了”还是“小了”都没有意义。同样，如果字典的页码是乱的，你也没法靠“翻到中间看页码再决定往前还是往后”来查词。二分查找对数据有三条硬性要求。

第一，数组必须有序。这里的“有序”指单调不减：前面的元素永远不大于后面的元素。这样“中间值比目标小”才能推出“目标只可能在后半段”。第二，必须支持随机访问——按下标 O(1) 拿到元素。数组做到了，但链表做不到：在链表里“跳到中间”要遍历，每次“砍半”都变成 O(n)，二分就失去了意义。第三，元素之间可以比较大小，而且比较方向不会突然反转。这三点合起来，才能保证每次“大了/小了”的判断是可靠的。

下次拿到一个题，先像检查游戏规则一样过一遍：数组有序吗？按下标能直接访问吗？元素能比较吗？如果答案是否定的，二分查找就不是你的第一选择。这就像面试官问“你能用二分吗”，你反手先问“数据是有序数组吗”——这份清醒本身就是加分项。

a0≤a1≤a2≤⋯≤an−1a_0 \le a_1 \le a_2 \le \cdots \le a_{n-1}
这就是有序数组的数学长相：从第一个元素到最后，一路不减。
  1. 下标起点数组下标从 0 开始，共 n 个元素
    a0,a1,…,an−1a_0, a_1, \ldots, a_{n-1}
  2. 相邻有序任意相邻两个元素，前一个不大于后一个
    ai≤ai+1,0≤i<n−1a_i \le a_{i+1}, \quad 0 \le i < n-1
  3. 全序可比任意两个元素都能比出大小，而不是“有的能比有的不能比”
    ∀i,j: ai≤aj 或 aj≤ai\forall i, j: \ a_i \le a_j \ \text{或} \ a_j \le a_i

区间写法：左闭右闭与左闭右开

玩猜数字时，你说“范围是 1 到 100”，100 到底算不算在候选里？如果说“包含 100”，那是闭区间；如果说“100 不算，但范围最多到它”，那就是半开区间。两种约定都能玩，可怕的是你一会儿用“含 100”一会儿又用“不含 100”，游戏规则自相矛盾。

代码里的二分查找同样有两种区间约定。左闭右闭 [left, right]：两边都包含，初始化 left = 0, right = n - 1，循环条件用 while (left <= right)，更新时 left = mid + 1 或 right = mid - 1。左闭右开 [left, right)：右边不包含，初始化 right = n，循环条件用 while (left < right)，更新时 left = mid + 1 或 right = mid。二者唯一共同点是 mid 的计算方式：

写代码前，先在注释里写明“我选的是左闭右开”，然后让初始化、循环条件、更新规则三者完全服从这个约定。一旦混用——比如循环写 left < right 但更新用 right = mid - 1——就会漏掉候选元素或陷入死循环。面试时用一个约定的好处是，边界情况可以从容推导，而不是靠试错。

mid=left+⌊right−left2⌋mid = left + \left\lfloor \frac{right - left}{2} \right\rfloor
这个式子用“左边界加区间长度的一半”求出中点，天然规避了 left + right 可能溢出的问题。
  1. 差值取半先算出区间长度 right - left，这个差值不会溢出
    right−leftright - left
  2. 向下取整整数除法取整后，mid 一定落在 [left, right] 内且偏向左边
    ⌊right−left2⌋\left\lfloor \frac{right - left}{2} \right\rfloor
  3. 加左偏移从 left 出发前进半段距离，得到中点下标
    left+⌊⋯ ⌋left + \lfloor \cdots \rfloor
  4. 循环条件对照左闭右闭要到 left 超过 right 才停；左闭右开到 left 等于 right 就停
    [l,r]: l≤r;[l,r): l<r[l, r]:\ l \le r; \qquad [l, r):\ l < r

查找变体：第一个与最后一个

猜数字游戏里，目标只有一个，猜中即赢。但工作中常有另一类需求：在一排按书名编号排列的书架上，找到“编号为 9 的第一本书”。书架上可能有好多本编号 9 的书，普通二分找到任意一本 9 就返回，并不能保证它是第一本。图书管理员的策略是：哪怕翻到一本 9，也继续往前翻，直到确认没有更靠前的 9。

对应到代码，这就是寻找“第一个等于 target”的变体。标准二分在 nums[mid] == target 时立刻返回；变体则把相等的情况也纳入收缩——只要中间值不小于 target，就把右边界移到 mid，让搜索继续向左压。循环结束后，left 停在“第一个不小于 target”的位置，再检查 nums[left] 是否等于 target 就能确认是否存在。

类似地，“最后一个等于”用 nums[mid] > target 收缩右边界，找到“第一个大于 target”的位置再减一。大于等于、小于等于这些变体，本质只改一个比较符号。图书管理员手里的诀窍就是：你想找哪个边界，就朝哪个方向收缩。

if nums[mid]≥target:right=midelse:left=mid+1\text{if}\ nums[mid] \ge target: \quad right = mid \qquad \text{else}: \quad left = mid + 1
把“等于就返回”改成“等于也收缩右边界”，就能找到最左边的目标值。
  1. 大于等于条件把相等情况并入右边界收缩，而不是直接返回
    nums[mid]≥targetnums[mid] \ge target
  2. 保留候选right = mid，因为 mid 本身可能就是第一个等于 target 的元素
    right←midright \leftarrow mid
  3. 排除严格小mid 元素严格小于 target，它及其左边都不可能是答案
    left←mid+1left \leftarrow mid + 1
  4. 循环退出left 已越过所有严格小于 target 的元素，成为首个候选
    返回 left\text{返回}\ left

插入位置：lower_bound 与 upper_bound

图书管理员还常遇到另一个问题：进了一批新书，要把书号 8 插进 [1, 3, 5, 7, 9] 这本书架，应该放在哪里？他不需要遍历，只需要找到“第一个编号不小于 8 的位置”——也就是 9 所在的下标 4，把新书插到 9 前面。这个位置有个专门的叫法：lower_bound，也就是“下界”。

lower_bound 正是上一节变体算法的产物：在有序数组中找到第一个“大于等于 target”的下标。如果 target 存在，它指向第一个 target；如果不存在，它指向应该插入的位置。它的镜像 upper_bound 找“第一个大于 target”的下标，二者合起来可以圈出所有等于 target 的元素区间 [lower_bound, upper_bound)。

这就像查字典时，你不仅想知道“这个词在不在”，还想知道“如果不在，它该插在哪两页之间”。二分查找真正擅长的是“找边界”，存在性只是顺带的判断题。面试中遇到“插入位置”“找第一个”“找最后一个”，全是这个思路。

P=min⁡{i∣nums[i]≥target},Q=min⁡{i∣nums[i]>target}P = \min\{ i \mid nums[i] \ge target \}, \qquad Q = \min\{ i \mid nums[i] > target \}
P 是插入位置，Q 减一得到最后一个等于 target 的位置。
  1. 下界集合收集所有满足“大于等于 target”的下标，取最小的那个
    min⁡{i∣nums[i]≥target}\min\{ i \mid nums[i] \ge target \}
  2. 上界集合把条件换成“严格大于”，得到第一个更大元素的位置
    min⁡{i∣nums[i]>target}\min\{ i \mid nums[i] > target \}
  3. 区间圈定所有等于 target 的元素恰好落在 [P, Q) 之间
    [P, Q)[P,\ Q)
  4. 空集兜底如果没有元素满足条件，P 就是数组长度 n，表示插在末尾
    P=n当集合为空P = n \quad \text{当集合为空}

易错边界：溢出与死循环

猜数字游戏里，如果朋友说“你报的数字比目标大，那目标可能等于这个数字，也可能比它大”，这个反馈本身就是矛盾的，游戏会陷入无限追问。二分查找里的边界错误也分两类：让循环永远跑不完，或者让答案从缝隙里溜走。

最常见的三个坑。第一个是死循环：某些写法更新 left = mid 而不是 mid + 1，当 left 和 right 相邻时，向下取整的 mid 等于 left，left 原地踏步，循环永不结束。第二个是越界访问：循环条件与更新规则不匹配，比如左闭右开却写 right = mid - 1，可能跳过候选，甚至访问到数组外。第三个是整数溢出：用 (left + right) / 2 计算 mid，当 left 和 right 都是很大的数时，相加可能超过整数上限。安全的写法是：

这三个坑的共同本质是“区间不变量被破坏”。所谓不变量，就是你在注释里写下的那句规则——“我维护的是一个左闭右开区间，right 永远指向区间外的第一个位置”。只要初始化、循环条件、更新三者和这句规则严格一致，死循环和越界就不会找上你。就像猜数字游戏，规则说清楚了，玩一百遍都不会拌嘴。

mid=left+⌊right−left2⌋(安全),⌊left+right2⌋(可能溢出)mid = left + \left\lfloor \frac{right - left}{2} \right\rfloor \quad (\text{安全}), \qquad \left\lfloor \frac{left + right}{2} \right\rfloor \quad (\text{可能溢出})
同号相减不会溢出，同号相加可能溢出——这是整数世界的常识。
  1. 溢出根源left 和 right 都接近 int 上限时，两者相加超界
    left+rightleft + right
  2. 安全差值right 大于 left，相减必然在安全范围内
    right−leftright - left
  3. 偏左取整奇数长度时 mid 偏向 left 一侧，符合整数除法的截断
    ⌊right−left2⌋\left\lfloor \frac{right - left}{2} \right\rfloor
  4. 配套前进既然 mid 偏左，就必须让 left = mid + 1，保证区间严格缩小
    left←mid+1left \leftarrow mid + 1

实战应用：旋转数组与工程落地

猜数字游戏有一个变种：把 1 到 100 按顺序排成一个环，在某个位置剪开再抻直，比如 [50, 51, ..., 100, 1, 2, ..., 49]。表面看数组不是全局有序，但环从剪口分成两段，每一段内部依然递增。你依然可以用“大了/小了”的思路：看中间值落在哪一段有序区间里，再判断目标在不在那段里。这就是旋转数组二分。

旋转数组，比如 [4, 5, 6, 7, 0, 1, 2]，本质是两段有序序列拼在一起。二分时先比较 nums[left] 和 nums[mid]：如果左边不大于中间值，说明左半段没有断点，是严格递增的；否则断点在左半段，右半段有序。判断出哪一半有序后，再看 target 是否落在这个有序区间里，从而决定往哪边收缩。

同理，峰值查找在局部单调的数组里也靠二分逼近。工程上更不用说：数据库的 B+ 树索引，每一层节点内部都是有序数组，查找时就是在做二分定位。面试时写出旋转数组二分，再点出“这与数据库索引的分层查找同源”，会让面试官觉得你不仅会背模板，还理解了二分在真实系统里的位置。

nums[l]≤nums[mid]  ⟹  [l,mid] 单调有序nums[l] \le nums[mid] \implies [l, mid]\ \text{单调有序}
旋转数组别看它“乱”，每一轮二分至少有一半是有序的，抓住有序半就能继续砍。
  1. 断点判断nums[l] 不大于 nums[mid]，说明左半没有跨过旋转断点
    nums[l]≤nums[mid]nums[l] \le nums[mid]
  2. 有序半区左半区间 [l, mid] 是单调递增的真正有序段
    [l,mid] 单调有序[l, mid]\ \text{单调有序}
  3. 命中判断target 落在这个有序区间内，就把搜索范围收缩到左半
    target∈[l,mid]  ⟹  r←mid−1target \in [l, mid] \implies r \leftarrow mid - 1
  4. 否则转右半target 不在有序半，就去另一半继续同样的逻辑
    l←mid+1l \leftarrow mid + 1

AI 应用场景

海量样本特征查询

阶段：数据检索与特征工程

解决的问题：AI 训练时频繁按样本 ID 查询特征，如果用线性扫描，十亿条记录平均要扫 5 亿次才能命中一条，训练根本无法进行。数据库在 B+ 树索引中每层用二分定位到目标页，页内再用二分锁定记录，把查询压缩到对数级。

具体案例：推荐系统的 user_item 行为表有 10 亿条记录，按 user_id 建索引后，一次点查从秒级降到毫秒级。如果把问题抽象成“有序数组中找目标”，正是猜数字游戏在大数据场景下的复现。

git bisect 二分定位坏改动

阶段：模型调试与归因

解决的问题：模型效果突然变差，几十次提交不知道是哪一次引入的回归。人工逐个检查又慢又容易漏。git bisect 用二分查找的思想，把一个“好的提交”和一个“坏的提交”之间的区间反复对半切。

具体案例：假设有 64 个可疑提交，git bisect 自动切到中间提交，你只需跑一次测试并告诉它“这个版本是好是坏”，约 6 轮就能定位到罪魁祸首。这就像猜数字游戏里“大了/小了”的判断，只是判断对象从数字变成了提交状态。

Python 演示

python45 行
def binary_search(nums, target):    # standard binary search, returns index or -1    left, right = 0, len(nums) - 1  # closed interval [left, right]    while left <= right:        mid = left + (right - left) // 2        if nums[mid] == target:            return mid        elif nums[mid] < target:            left = mid + 1        else:            right = mid - 1    return -1  def lower_bound(nums, target):    # first index with nums[i] >= target, works as insert position    left, right = 0, len(nums)  # half-open interval [left, right)    while left < right:        mid = left + (right - left) // 2        if nums[mid] >= target:            right = mid        else:            left = mid + 1    return left  def upper_bound(nums, target):    # first index with nums[i] > target    left, right = 0, len(nums)    while left < right:        mid = left + (right - left) // 2        if nums[mid] > target:            right = mid        else:            left = mid + 1    return left  if __name__ == "__main__":    nums = [1, 3, 5, 7, 9, 9, 11]    print("standard find 9:", binary_search(nums, 9))    print("lower_bound 9:", lower_bound(nums, 9))    print("upper_bound 9:", upper_bound(nums, 9))    print("insert position 8:", lower_bound(nums, 8))    print("insert position 12:", lower_bound(nums, 12))
目的：一次性实现标准二分、lower_bound 和 upper_bound 三个函数，覆盖“找目标”“找第一个”“找插入位置”三类高频面试场景。
  1. left, right = 0, len(nums) - 1 # closed interval [left, right]左闭右闭区间，right 指向最后一个候选元素
  2. while left <= right:闭区间在 left 与 right 相等时还有最后一个元素要检查
  3. mid = left + (right - left) // 2用差值防溢出，同时避免了 left + right 相加的风险
  4. elif nums[mid] < target:中间值比目标小，说明目标只可能在右半
  5. left = mid + 1left 必须跳过 mid，否则区间不缩小
  6. left, right = 0, len(nums) # half-open interval [left, right)左闭右开，right 初始化为长度，不包含任何元素
  7. while left < right:半开区间下 left 等于 right 说明区间已空
  8. if nums[mid] >= target:大于等于号是 lower_bound 的灵魂
  9. right = mid保留 mid 作为候选，因为 mid 可能就是第一个满足条件的元素

常见误区

误区“我 while 条件写 left < right，然后更新 right = mid - 1，这有什么问题？我觉得这样也能跑通。”

正解左闭右开 [left, right) 中，right 本身不参与候选，right = mid - 1 会把 mid - 1 这个位置也排除掉，可能跳过答案；同时破坏区间不变量，导致漏查或越界。就像游戏规则说“范围到 100 但不含 100”，你却把 100 当候选来排除，规则自相矛盾。两种写法都对，但必须整条链路保持一致。

为何常见：两种写法代码长得极像，初学者往往是凭记忆拼凑，没有意识到初始化、循环条件、更新规则三者是绑定关系。

误区“mid = (left + right) // 2 简单好记，平时跑起来也没出过问题，为什么大家都用 left + (right - left) // 2？”

正解当数组长度接近整数上限时，left + right 会溢出成负数，mid 变成负数导致越界访问。差值写法 right - left 是两个同号整数相减，结果一定在安全范围内。就像两个大数相加超过了你的计分板显示上限，但相减永远在量程内。

为何常见：日常测试数据太小，溢出根本不触发，导致很多开发者从未意识到这个隐患，而面试官恰好爱考这种工程细节。

误区“left = mid 而不是 mid + 1，这样 mid 也可以成为新的下界，应该更保守更安全。”

正解当 left + 1 == right 时，向下取整的 mid 等于 left，执行 left = mid 后 left 原地不动，循环永不终止。必须 left = mid + 1 才能让区间严格缩小。这与“mid 偏左取整”是配套的：既然 mid 可能等于 left，左边界就必须+1。

为何常见：初学者以为“保守”就是包含 mid，却没意识到整数向下取整会让 mid 粘在左边界上，区间失去收缩能力。

误区“二分查找就是判断元素在不在数组里，找不到就返回 -1，仅此而已。”

正解二分查找的本质是“找第一个满足条件的位置”。lower_bound 在目标不存在时返回的插入位置，正是这种本质的体现。理解了这一点，插入位置、第一个/最后一个等值等变体题就全是同一个模板。“存在性”只是“找边界”的副产品。

为何常见：教科书通常先教标准查找，用“返回下标或 -1”作为唯一结果，容易把思维固化在等值查询上。

误区“二分查找必须先有全局有序数组，旋转数组这种乱序结构怎么能二分？”

正解旋转数组由两段有序序列拼接而成，每一轮二分至少有一半是严格有序的，判断 target 是否落在有序半即可继续收缩。峰值查找也利用了局部单调性。二分真正依赖的是“可判断的单调性”，不一定是全局单调。

为何常见：教科书上“二分查找适用于有序数组”的限定词被误解成“全局有序”，忽略了旋转数组这类局部有序的应用。

面试题

Q1. 标准二分查找能正确工作的首要前提是什么？

单选题 · easy

  • A.数组有序且支持随机访问← 正确答案
  • B.数组无序但元素唯一
  • C.数组用链表存储即可
  • D.数组长度必须是 2 的幂

答案：A。二分靠比较中间值与目标来排除一半区间，这要求数组按序排列；同时要能瞬间按下标访问元素，链表做不到（跳到中间要 O(n)）。就像猜数字游戏必须先保证范围单调，且你能直接报到中间的数。

Q2. 左闭右闭写法中正确的循环条件是？

单选题 · easy

  • A.while (left < right)
  • B.while (left <= right)← 正确答案
  • C.while (left != right)
  • D.while (left == right)

答案：B。左闭右闭 [left, right] 表示 left 和 right 都可能包含答案，当 left == right 时还有一个元素未检查，所以必须用 <= 把相等情况包含进来。这就像游戏里“范围 1 到 100，100 也算在内”，那当范围收窄到“50 到 50”时你还得看一眼 50。

Q3. 二分查找的时间复杂度是？

单选题 · easy

  • A.O(1) 常数时间
  • B.O(log n) 对数时间← 正确答案
  • C.O(n) 线性时间
  • D.O(n log n) 线性对数

答案：B。每轮比较后区间缩小一半，规模从 n 到 n/2 再到 n/4，共约 log2(n) 轮。100 万元素只需约 20 次比较，这就是猜数字 1 到 100 最多 7 次必中的数学原因。

Q4. 下列哪些 mid 写法可以避免 (left + right) 整数溢出？

多选题 · mid

  • A.(left + right) / 2 直接计算
  • B.left + (right - left) / 2 计算← 正确答案
  • C.(left + right) >>> 1 无符号移位← 正确答案
  • D.right - (right - left) / 2 计算← 正确答案

答案：BCD。B 用差值避免两个大数相加；C 用无符号右移让溢出后的负数恢复为正确位置；D 从右边界往回走一半，同样基于差值，只是 mid 偏向右边。A 是典型的溢出写法，left + right 超过 int 上限就会变成负数。

Q5. 含重复元素的有序数组 [1, 3, 5, 7, 9, 9, 11] 中查找第一个 9，使用 nums[mid] >= 9 收缩右边界，循环结束后 left 指向什么？

单选题 · mid

  • A.第一个 9 的位置← 正确答案
  • B.最后一个 9 的位置
  • C.第一个大于 9 的元素
  • D.位置不确定是随机的

答案：A。>= 条件让等于 target 的元素也触发右边界收缩，相当于不断向左逼近。循环结束后 left 停在“第一个不小于 9”的位置即下标 3；再检查 nums[left] == 9 即可确认存在。图书管理员“翻到 9 也继续往前翻”就是这个过程。

Q6. 有序数组 [1, 3, 5, 7, 9, 11] 中 lower_bound(8) 的返回值是？

单选题 · mid

  • A.下标 4 表示 8 的插入位置← 正确答案
  • B.下标 3 表示 7 所在的位置
  • C.下标 5 表示数组末尾位置
  • D.返回 -1 表示 8 不存在

答案：A。第一个不小于 8 的元素是 9，下标为 4，所以 lower_bound 返回 4，表示 8 应插在 7 和 9 之间。标准查找会返回 -1，但 lower_bound 不关心“是否存在”，只关心“边界在哪”，这正是插入位置类题目的核心。

Q7. 左闭右开 [left, right) 写法循环退出后 left 的正确语义是？

单选题 · hard

  • A.第一个不小于 target 的位置← 正确答案
  • B.最后一个小于 target 的位置
  • C.一定是 target 的精确位置
  • D.第一个大于 target 的位置

答案：A。左闭右开中 right 是区间外边界，循环里若 nums[mid] >= target 则 right = mid 保留候选，否则 left = mid + 1 排除严格小的元素。结束时 left 与 right 重合，恰好是第一个不小于 target 的下标；若想找精确位置，还需判断这个下标上的值是否等于 target。

Q8. 旋转数组 [4, 5, 6, 7, 0, 1, 2] 中查找 0，第一步应如何判断？

单选题 · mid

  • A.直接比较 0 和中间值 7 就足够
  • B.先判断左半或右半哪边有序← 正确答案
  • C.直接把数组再旋转回原状
  • D.旋转数组无法进行二分查找

答案：B。旋转数组由两段有序序列构成，第一步应比较 nums[left] 与 nums[mid]：nums[0]=4 <= nums[3]=7，说明左半 [4,5,6,7] 严格有序。target=0 不在这段，于是去右半继续。这就是“先找有序半区，再判断目标归属”的标准套路。

Q9. 关于含重复元素数组的二分变体，正确的说法包括？

多选题 · mid

  • A.第一个等值用大于等于收缩← 正确答案
  • B.最后一个等值用大于号收缩← 正确答案
  • C.等值分支也可以直接返回答案
  • D.变体依赖边界条件保持一致← 正确答案

答案：ABD。找第一个等于 target 时，nums[mid] >= target 让右边界收缩，答案向左压；找最后一个等于时，用 nums[mid] > target 先找“第一个大于 target”再减一。C 错误，因为标准查找在等值分支直接返回得到的是“任意一个”等值位置，不保证是第一个或最后一个。变体题特别考验区间定义是否自洽。

Q10. 以下哪些情况会导致二分查找出现死循环？

多选题 · hard

  • A.left = mid 且 mid 向下取整← 正确答案
  • B.right = mid 且 mid 向上取整← 正确答案
  • C.循环用左闭右开且 left = mid + 1
  • D.找到 target 后不返回也不移动指针← 正确答案

答案：ABD。向下取整时 mid 可能等于 left，left = mid 让左边界原地踏步；向上取整时 mid 可能等于 right，right = mid 让右边界原地踏步。两者都可能让区间不缩小。C 是标准左闭右开写法，left 严格右移，不会死循环。D 命中后既不返回也不动指针，循环条件永不满足退出。