二分查找时如何避免 int 型 mid 溢出？｜腾讯算法面经解析

60 秒回答模板

可以这样回答：二分查找中如果用 (left + right) / 2 计算 mid，当 left 和 right 都很大时可能发生整数溢出。更稳的写法是 left + (right - left) / 2，或在语言允许时使用无符号右移/更大整数类型。 right - left 不会超过数组长度范围，再加回 left 可以得到同样的中点位置，却避免 left+right 先溢出。实现时还要保证每次循环都收缩区间，否则可能死循环。闭区间 [l,r] 写法直观，但要处理 l <= r 和 r = mid - 1；左闭右开 [l,r) 更适合 lower_bound 类问题。关键是保持不变量一致，不要混用两种边界。要处理空数组、目标不存在、重复元素、查找第一个/最后一个满足条件的位置，以及语言整数上限。不同语言整数溢出行为不同，C/C++ signed overflow 还涉及未定义行为。验证时重点看：验证用例包括空数组、单元素、目标在首尾、不存在、重复值、极大下标和左右边界相邻时的终止情况。

考点 考点边界

主线 核心机制

易错点 只改 mid 公式，没有说明区间不变量和收缩规则。

深入解析

考点边界

这题不是普通二分模板，而是考察有序性、边界收缩和整数溢出。回答要同时说明 mid 安全计算、循环不变量、闭区间或左闭右开区间的更新规则。本题对应“二分查找 mid 溢出处理”，核心前提是：二分查找中如果用 (left + right) / 2 计算 mid，当 left 和 right 都很大时可能发生整数溢出。更稳的写法是 left + (right - left) / 2，或在语言允许时使用无符号右移/更大整数类型。

核心机制

right - left 不会超过数组长度范围，再加回 left 可以得到同样的中点位置，却避免 left+right 先溢出。实现时还要保证每次循环都收缩区间，否则可能死循环。关键证据要落到状态转移、不变量、边界用例、复杂度来源，这样才能说明机制为什么能支撑题目结论。如果继续展开，要说清状态定义、不变量、边界更新、终止条件和复杂度来源，并用反例说明为什么相邻做法不成立。

关键取舍

闭区间 [l,r] 写法直观，但要处理 l <= r 和 r = mid - 1；左闭右开 [l,r) 更适合 lower_bound 类问题。关键是保持不变量一致，不要混用两种边界。因此要用输入规模、额外空间、最坏复杂度和边界用例来决定方案，而不是只背一个平均复杂度。这些取舍决定了方案在不同输入规模、延迟、内存、并发、泛化或一致性要求下是否仍然成立。

边界风险

要处理空数组、目标不存在、重复元素、查找第一个/最后一个满足条件的位置，以及语言整数上限。不同语言整数溢出行为不同，C/C++ signed overflow 还涉及未定义行为。排查时优先用空输入、重复值、极端有序数据、溢出、内存上限和复杂度退化样例验证。需要特别关注极端输入、数据分布变化、资源不足、并发竞争或观测口径错误带来的退化。修复时要用最小反例复现错误，再检查边界条件、循环不变量、数据结构选择和复杂度退化点。

验证抓手

验证时要覆盖空输入、单元素、重复元素、边界溢出、极端有序或逆序数据，并明确时间复杂度和空间复杂度。能说出为什么这个复杂度成立，比只写伪代码更可靠。针对本题，最有价值的验证信号是：验证用例包括空数组、单元素、目标在首尾、不存在、重复值、极大下标和左右边界相邻时的终止情况。把验证抓手说出来，可以让答案从知识点延伸到算法正确性、复杂度和边界用例验证。

易错点

只改 mid 公式，没有说明区间不变量和收缩规则。
忽略重复元素、目标不存在和边界相邻时的终止条件。
把相邻概念混用，没有明确说明这道题真正考察的边界。
没有给出验证方式，导致答案听起来完整但无法判断是否真的生效。

面试官追问

为什么 left + (right-left)/2 更安全？

它避免先计算可能超过整数上限的 left+right。right-left 表示区间长度，通常受数组长度约束，再加 left 能得到同样的中点。

二分最容易写错的边界是什么？

最常见是循环条件和区间更新混用，例如闭区间却写成右开区间更新，导致漏掉元素或死循环。写法要围绕不变量保持一致。回答时还要补充适用前提、失败场景和验证信号，避免只给一个孤立结论。

“二分查找时如何避免 int 型 mid 溢出”继续追问时最该补哪条边界？

应该围绕“二分查找 mid 溢出处理”补适用前提、失败场景和验证证据。先说明哪些条件下这个机制成立，再说明哪些输入规模、并发状态、数据分布或资源限制会让答案需要调整。

“二分查找时如何避免 int 型 mid 溢出”怎样回答才不是只背概念？

看它能否把“二分查找 mid 溢出处理”的机制链路、关键取舍和可观测信号连起来。回答时应落到具体状态变化、数据路径、复杂度、指标或排查工具，而不是只复述定义。

“二分查找时如何避免 int 型 mid 溢出”怎么判断算法选型？

先看是否有最优子结构、单调性、局部选择是否会影响全局最优，以及数据结构能否降低查找或更新成本。动态规划、贪心、二分、哈希、堆和树结构分别对应不同的不变量。