关于求mid的注意事项二

[casablancaml]

求mid时除了不能直接用(left + right) / 2来运算以防止上溢外，还有一个主意事项如下：
这里为什么必须要用 left + (right - left) / 2 而不是 right - (right - left) / 2 呢？按理说它们是等价的呀？
其实不等价，因为当 right - left 不能被2整除时， (right - left) / 2 得到的是下取整的结果，
例如5/2得到的是2而不是3。因此用 right 去减这个结果时，mid的值就会偏大，那么在最后一次循环检查
数组元素时就会错位或者越界。举例：假设left = 5, right = 18，那么 left + (right - left) / 2
的结果是11，而 right - (right - left) / 2 的结果则是12.

当在极端情况下，假设数组只有一个元素，那么 mid = right - (right - left) / 2 = 1，访问nums[1]就越界了。
但是如果用 mid = left + ((right - left) / 2 ) = 0，nums[0]就OK.

另一种情况也是如此，假设target比数组中的最大值还大，那么当left移动到了最后一个元素位置即 `nums.length

• 1时，right 始终等于 nums.length，那么mid = right - (right - left) / 2就得到 nums.length，于是 访问 nums[nums.length] 就会越界啦。相反如果mid = left + ((right - left) / 2 )`，则得到mid == left，因
  此访问 nums[nums.length - 1] 没有问题，是最后一个元素。