第 6 节 关于 mid = (left + right) / 2 的说明

结论：

• 绝大多数情况下，用 mid = (left + right) / 2 （默认） 或者 mid = (left + right + 1) / 2 （取中间数上取整）；
• 如果 left + right 在 int 范围里会溢出，使用 mid = left + (right - left) / 2 或者 mid = left + (right - left + 1) / 2； 使用「位移运算」代替「除以 2」在绝大多数情况下不是必要的。

整数除法不可能取到真正的中间的元素

事实上，在区间里有偶数个元素的时候，位于中间位置的元素有 个。

mid = (left + right) / 2 有整型溢出的可能

我们写一段代码验证一下：

int left = Integer.MAX_VALUE - 10;
int right = Integer.MAX_VALUE - 8;
int mid = (left + right) / 2;
int mid2 = left + (right - left) / 2;
System.out.println("mid = " + mid);
System.out.println("mid2 = " + mid2);

输出：

mid = -10
mid2 = 2147483638

解决办法其实上面的代码已经给出了，写成 left + (right - left) / 2; 就可以。

但是，如果题目中给出的数据范围 left + right 不会发生整型溢出，写成 mid = (left + right) / 2 是没有问题的。

用位运算代替整数除法

由于正整数右移一位，相当于将这个正整数除以 2 ，因此还可以将除法操作改为右移 1 位。

int left = Integer.MAX_VALUE - 10;
int right = Integer.MAX_VALUE - 8;
int mid = left + ((right - left) >> 1);
System.out.println("mid = " + mid);

输出：

mid = 2147483638

注意：右移操作的优先级问题，不同语言的规定不一样。在 Java 中，上面的 ((right - left) >> 1) 最外面的括号必须加。

理论上，右移 1 位是比除以 2 快的，但是这种快也快不了多少，并且现代编译器会自己将除以 2 转换为右移 1 位，因此没有必要写成右移，知道有这么个知识点就可以了。

无符号右移

「无符号右移」运算是这样规定的：不管整数是正是负，右移以后最高位都补 。因此在 left + right 整型溢出的时候，

int mid = (left + right) >>> 1;

依然可以得到正确的值，我们写代码验证一下：

int left = Integer.MAX_VALUE - 10;
int right = Integer.MAX_VALUE - 8;
int mid = (left + right) >>> 1;
System.out.println("mid = " + mid);

输出：

mid = 2147483638

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search/explanation 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。