归并排序中的合并时中间索引的求解问题
注：这篇文章主要阐述书写归并排序是遇到的一个问题，不涉及归并排序的具体实现
踏坑初体验
之前在《剑指Offer》中看到二分查找的代码中，求中间索引的点没有用 常规的
方法一、int mid = (r - l) / 2; 而是用了 方法二、int mid = l + (r - l) / 2;
当时推导了一下两种实现的目的都是为了计算 l 和 r 之间的索引位置，也就没有继续思考为什么要具体这样做；今天在复习归并排序时又遇到了同样情况：计算拆分数组的中间索引同样要用到上面的方法；所以自己就具体网上搜索看了一下：
原来真的没有无中生有的事情，各种改进都是有原因的，采用第一种写法时，如果两个边界的和大于了2的31次方，被除数将会超出 int 类型的最大范围，从而导致溢出。
图1 两个边界差的一半再加上小边界
多想点，就又有收获了
如果只是前面那样替换完就结束了，那这篇文章也就没啥大的意义了，接着看~~~~
如果看过集合框架的jvm源码就会发现，在源码中基本上不会出现 '/' 和 ‘%’ 等符号；因为使用位 运算会达到除以2的倍数和取余的效果，并且效率要高于‘/’ 和 '%'；因此我把代码做了如下改动：（注意：这里我是删除了一整行，然后又重新敲了一遍）
图2 除以2改为右移还有~~~~
改动了上面一行代码，迫不及待的传入测试用例想看下结果，运气不好，破天荒的报了一个内存栈溢出的错误。这~~~~~ 不应该呀！（上次测试过的呀，递归可以正常退出的呀）
图3 都是删除一整行惹得祸
调试新收获
小学老师教过我们，遇到问题就要解决它，而不是放下：开始加了断点 dubug(假设初始r = 5,l = 0)
发现在求mid的过程比较坎坷：
mid = r - (r - l) >>> 1 = 5 - (5 - 0) / 2 = 3 ====> mergeSort(arr,0,3);
mid = r - (r - l) >>> 1 = 3 - (3 - 0) / 2 = 2 ====> mergeSort(arr,0,2);
mid = r - (r - l) >>> 1 = 2 - (2 - 0) / 2 = 1 ====> mergeSort(arr,0,1);
mid = r - (r - l) >>> 1 = 1 - (1 - 0) / 2 = 1 ====> mergeSort(arr,0,1);
问题已经出来，递归调用了4次，原理上应该l == r,该返回了；但是程序却陷入了l = 0,r = 1的死循环，永远也不会达到退出递归的条件：l <= r。
写到这里，很多人可能已经发现了问题的所在，我就不卖关子：
mid = (r + l) >>> 1;
mid = l + (r - l) >>> 1;
mid = r - (r - l) >>> 1
不错，大家请移步图2仔细看看，我本来只是想将 ‘/’ 改为 ‘>>>1’; 然而没想到"数学系脑细胞“泛滥；将求中点值的方法改了
mid = l + (r - l) >>> 1 变为了 mid = r - (r - l) >>> 1
个人感觉这两种解法是没有区别的，但是测试代码时第二种方法的确有问题~~~~~
好了问题来了，那位大神可以帮我解答这个问题？评论区见~~~~~~~
网友评论