Java二分查找两种mid计算方式的区别及优劣对比

核心区别 #

两种写法在low + high无整数溢出时计算结果完全一致，核心差异体现在溢出场景下的行为表现：

• int mid = (low + high) / 2 属于有符号整数除法：Java中int是32位有符号整数，最大值为2^31-1（即2147483647），如果low和high的和超过这个上限会触发整数溢出，得到负的int值，此时除以2得到的mid也是负数，作为数组下标访问时会直接抛出越界异常。
  举个实际场景的例子：当low=2147483640，high=2147483645时，两数真实和为4294967285，溢出后得到的int值为-11，执行-11/2得到结果-5，属于完全非法的数组下标。
• int mid = (low + high) >>> 1 属于无符号右移运算：>>>是Java的无符号右移操作符，不管low+high是否溢出为负数，右移1位的逻辑等价于对两数之和做无符号除以2取整，哪怕和溢出成负数，最终得到的mid依然是正确的非负中间值。
  还是上述例子，溢出得到的-11执行-11 >>> 1后得到2147483642，正好是low和high对应的正确中间位置，不会触发下标异常。

写法优劣结论 #

int mid = (low + high) >>> 1是更优的实现，核心优势是鲁棒性更强：

• 彻底规避了大数组场景下low、high求和溢出导致的下标越界问题，哪怕数组长度接近int类型上限，也能正确计算中间索引；
• 位运算的执行效率不低于整数除法，没有额外性能开销，写法也更简洁。

注：另一种常见的防溢出写法mid = low + (high - low)/2和无符号右移写法效果一致，只是实现思路不同。

无符号右移版本二分查找Java实现 #

class Solution {
    public int search(int[] nums, int target) {
      int low = 0;
      int high = nums.length - 1; 
      while(low <= high)
       { 
            int mid = (low + high) >>> 1;
            if(nums[mid] == target)
                return mid;
            if(target > nums[mid])
                low = mid + 1;
            else
               high = mid - 1;  
      }       
        return -1;    
    }
}

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