二分查找中mid = start/2 + end/2与mid = (start+end)/2的计算差异

在二分查找算法中，理论上mid = (start + end)/2、mid = start/2 + end/2、mid = start + (end - start)/2这三个表达式等价，但实际计算却会得到不同结果。

以下是一段用二分查找寻找数组元素最后一次出现位置的代码：

int lastOccurrence(vector<int> arr, int size, int key){
    int start = 0, end = size - 1;
    int last = -1;
    // int mid = start/2 + end/2;
    int mid;
    while(start <= end){
        // mid = start + (end - start)/2;
        mid = (start + end)/2;
        if(key == arr[mid]){
            last = mid;
            start = mid + 1;
        }
        else if(key > arr[mid]){
            start = mid + 1;
        }
        else{
            end = mid - 1;
        }
        cout << "start: " << start << "	end: " << end << "	mid: " << mid << endl;
    }
    return last;
}

传入的参数如下：

int main(){
    vector<int> arr = {1,2,3,4,4,4,4,5,6,7,11};
    int size = arr.size();
    int key = 4;
    cout << "First occurrence of " << key << " is at index " << firstOccurrence(arr, size, key) << endl;

    cout << "Last occurrence of " << key << " is at index " << lastOccurrence(arr, size, key) << endl;

    return 0;
}

算法逻辑为：当mid位置元素等于目标key时，记录索引并将start更新为mid+1以继续查找右侧；若key小于mid元素则将end更新为mid-1查找左侧，反之则更新start查找右侧。

实际使用mid = start/2 + end/2与mid = (start + end)/2时得到了不同结果，请问计算过程中二者的差异是如何产生的？

差异的核心在于C++中整数除法的截断规则：整数除法会直接舍弃小数部分，向零取整。两个表达式的计算顺序不同，导致截断的时机不一样，最终结果出现偏差。

举两个典型例子：

1. 当start=5，end=6时：
   • (start + end)/2：先求和得到11，除以2后截断小数部分，结果为5。
   • start/2 + end/2：先分别计算5/2=2、6/2=3，相加后结果也是5，此时二者一致。
2. 当start=5，end=7时：
   • (start+end)/2：求和得12，除以2结果为6。
   • start/2 + end/2：分别计算5/2=2、7/2=3，相加后结果为5，和前者出现明显差异。

这种差异的本质是：当start和end为一奇一偶或两个奇数时，各自先做除法会提前截断小数部分，导致最终求和结果比先求和再除法的结果少1（当两个数都是奇数时）或出现其他偏差。

在你的二分查找场景中，mid值的偏差会导致查找区间的偏移，进而影响最后一次出现位置的判断逻辑，最终得到不同的结果。

另外补充：mid = start + (end - start)/2这个表达式不仅能避免start+end的整数溢出问题（当start和end接近int类型最大值时，start+end会超出int范围导致溢出），而且在无溢出的情况下，计算结果和(start+end)/2完全一致，是二分查找中mid计算的最优写法。

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