用 (low + high) >>> 1 可防整数溢出导致的负索引越界,因无符号右移将溢出负值转为合法正索引;安全前提包括括号保障优先级、索引有效、区间左闭右闭及指针更新排除已检位置。

直接用 (low + high) / 2 算中间索引,在大数组或边界值场景下极易整数溢出,导致结果为负数——而数组下标一用负数,Java 或 C++ 不报错也不抛异常,而是静默越界访问,后续行为完全不可预测。无符号右移 >>> 是一种被验证有效的防御手段,关键不在“快”,而在“稳”。
为什么溢出会静默发生
有符号整型相加溢出时,不触发异常,只按补码规则截断。比如 Java 中:int low = Integer.MAX_VALUE - 1; // 2147483646int high = Integer.MAX_VALUE; // 2147483647int sum = low + high; // 实际得 -2(补码解释)
再除以 2 得到 -1,用作数组下标就直接越界,但程序可能继续跑、返回错误结果、甚至崩溃在别处,极难定位。
无符号右移如何切断溢出传导
>>> 把整个数值当 32 位(或 64 位)无符号整数看待,高位一律补 0,不关心符号位。所以即使 low + high 溢出变负,它的二进制形式仍被当作一个很大的正整数处理:
-
-2的 32 位补码是11111111 11111111 11111111 11111110 -
-2 >>> 1直接右移一位,高位补 0 →01111111 11111111 11111111 11111111,即2147483647 - 这个值虽不是数学意义上的中点,但仍是合法非负索引,不会导致静默越界
安全写法与必须配合的前提
仅靠 >>> 不够,它只是防溢出环节的一环。真正安全需满足:
- 始终用
mid = (low + high) >>> 1,不要省略括号,避免运算符优先级陷阱 -
low和high必须是有效数组索引(≥ 0 且 ≤nums.length - 1),不能是元素值或其他任意整数 - 区间定义统一为左闭右闭:
low = 0,right = nums.length - 1 - 更新指针时严格排除已检位置:
low = mid + 1或right = mid - 1,防止死循环
更推荐的替代方案(尤其跨语言)
如果项目需兼顾 Java/C++/Python 或未来可维护性,建议优先用减法形式:
-
mid = low + ((high - low) >> 1)—— 无溢出风险,语义清晰,所有语言通用 - C++20 起可用
std::midpoint(low, high),类型安全且自动处理溢出 - 对索引范围极大(如
size_t)或不确定符号的场景,显式转无符号类型再运算,例如(static_cast<uint64_t>(low) + high) >>> 1</uint64_t>











