二分查找中两种mid位置计算方式的差异是什么？

这两种计算方式的核心差异在于整数除法取整方向不同，最终会影响mid在区间中的偏向位置，进而左右二分查找的边界收缩逻辑：

1. int mid = left + (right - left) / 2 #

• 本质是对区间长度right-left做向下取整后，加上左边界left，得到的是偏向左边界的中间位置（左中点）。
• 示例：
  • 区间[1,4]（长度3，奇数）：(4-1)/2=1，mid=1+1=2，取左中点
  • 区间[2,5]（长度3，奇数）：(5-2)/2=1，mid=2+1=3，取左中点
  • 区间[1,5]（长度4，偶数）：(5-1)/2=2，mid=1+2=3，此时左右中点重合

2. int mid = right - (right - left) / 2 #

• 本质是用右边界right减去区间长度的向下取整值，等价于对区间长度做向上取整，得到的是偏向右边界的中间位置（右中点）。
• 示例：
  • 区间[1,4]（长度3，奇数）：(4-1)/2=1，mid=4-1=3，取右中点
  • 区间[2,5]（长度3，奇数）：(5-2)/2=1，mid=5-1=4，取右中点
  • 区间[1,5]（长度4，偶数）：(5-1)/2=2，mid=5-2=3，此时左右中点重合

二分查找中的实际影响 #

• 当需要收缩右边界（right = mid）时，用左中点计算可避免死循环，适合寻找第一个满足条件的元素场景。
• 当需要收缩左边界（left = mid）时，用右中点计算可避免死循环，适合寻找最后一个满足条件的元素场景。

注意：两种写法都规避了(left+right)/2可能出现的整数溢出问题，这是它们相对于传统写法的共同优势。

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