算法小细节之数组某部分的中间位置的索引

给定一个数组的某个部分，这部分起始索引为L，结束索引为R，求这部分中间位置的索引。

1. int mid = (L + R) / 2

这个公式在数学上没有任何错误，通过这样的方式得到的mid值一定是L和R的中间值，但是在计算机中可能会造成数值越界的问题，如果L接近Integer.MAX_VALUE，R也接近Integer.MAX_VALUE，那么(L + R)将会越界，返回一个不正确的值，例如：

public static void main(String[] args) {

    int i1 = Integer.MAX_VALUE - 10;
    int i2 = Integer.MAX_VALUE - 20;
    int i3 = i1 + i2;
    
    System.out.println(i3);  // 结果是-32
}

虽然我们不会定义一个那么长的数组，但为了程序的绝对正确性，这个求中间索引的方法需要改进，就是下面的第二种方法。

2. int mid = L + (R - L) / 2

这种方法就避免了在计算机中的值越界问题，但还可以改进，看下面的第三种方法。

3. int mid = L + ((R - L) >> 1)

在计算机中，移位运算是要比算术运算的效率高的，我们知道，一个数右移一位的结果与这个数除以2的结果是相同的（关于位运算的详细介绍可以参考图解JAVA位运算），所以这样把除以2改为右移一位来提高运行效率。