二分查找中mid = left + ((right - left) >> 1)的原理与效率优势

一、这条语句的工作逻辑 #

咱们拆解来看：

• 第一步计算right - left：当前搜索区间是左闭右开（left是区间起点，right是区间终点的下一位，初始值right = nums.len()），这个差值就是当前区间的实际长度。
• 第二步(right - left) >> 1：这是无符号整数的右移一位操作，对于非负整数来说，右移一位等价于把数值除以2并向下取整。比如5 >> 1得到2，4 >> 1得到2，和整数除法/2的结果完全一致。
• 最后加上left：把减半后的偏移量加到左边界上，就得到了当前区间的中间位置索引。

这里特意不用(left + right) / 2，核心是为了避免整数溢出：如果left和right都是接近usize类型最大值的数，直接相加会超出类型的取值范围，导致计算出错误的mid值。而right - left因为循环条件left < right的保证，肯定不会溢出，再加上left就安全多了。

二、和left + ((right - left)/2)功能一致但更快的原因 #

功能一致的核心原因 #

对于非负整数，右移一位和除以2的数学效果完全相同：

• 当right - left是偶数时，比如8，8 >> 1和8/2都得到4；
• 当right - left是奇数时，比如7，7 >> 1和7/2都得到3（整数除法默认向下取整）。
  所以两个表达式算出的mid值没有任何区别。

速度更快的本质原因 #

• CPU的**位运算（右移>>）**是硬件原生支持的简单操作，只需要1个时钟周期就能完成；
• 而整数除法/的运算逻辑复杂得多，需要多个时钟周期才能执行完毕（尤其是64位整数的除法指令，延迟远高于位运算）。

虽然现代编译器可能会把/2优化成右移，但直接写>>1能确保编译器采用最直接高效的位运算实现，不会因为某些特殊场景（比如编译器优化策略限制）导致性能打折扣。

三、结合代码场景看实际作用 #

在给定的Rust二分查找代码里，left和right都是usize类型（无符号整数），循环条件left < right保证了right - left是非负的，所以右移操作完全安全。每次计算mid后，通过比较nums[mid]和target调整边界，最终找到目标值的插入位置，整个过程中mid的计算既避免了溢出问题，又最大化了执行效率。

内容的提问来源于stack exchange，提问作者Unwashed Player