二分查找中mid的设置方法：如何避免int溢出问题

在LeetCode解决「278. 第一个错误的版本」问题时，使用二分查找会遇到隐藏陷阱：用m = (start + end)/2计算中间索引，在数组规模接近int最大值时会触发整数溢出，导致代码运行失败；而m = start + (end - start)/2能避免这个问题，以下是具体分析：

1. 存在溢出问题的代码（大数组场景下失败） #

public int FirstBadVersion(int n) {
    if(n == 1){
        return 1;
    }
    
    int s = 1;
    int e = n;
    int x = 0;
    while(s != e){
        x = (s+e)/2;
        if(IsBadVersion(x)){
            e = x;
        }
        else{
            s = x + 1;
        }
    }
    
    return s;
}

2. 避免溢出的正确代码（可正常运行） #

public int FirstBadVersion(int n) {
    if(n == 1){
        return 1;
    }
    
    int s = 1;
    int e = n;
    int x= 0;
    while(s != e){
        // x = (s+e)/2;
        x = s + (e-s)/2;
        if(IsBadVersion(x)){
            e = x;
        }
        else{
            s =  x + 1;
        }
    }
    
    return e;
}

核心原因分析 #

• 整数溢出问题：Java中int类型的取值范围是-2147483648到2147483647。当start和end都接近2147483647时，start + end的计算结果会超出int的最大值，触发溢出——此时结果会变成负数，再除以2得到的中间索引完全不符合预期，直接导致二分查找逻辑混乱，最终代码运行失败。
• 安全计算的原理：start + (end - start)/2的计算逻辑更安全：
  1. 首先计算end - start，由于start ≤ end，这个结果必然小于等于end，不会超出int的取值范围；
  2. 除以2后得到start到end区间长度的一半；
  3. 加上start后，结果正好是区间的中间索引，且始终在start和end之间，不会触发溢出。

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