计算中间节点问题
来源：1-2 归并过程
404_
2023-05-31 15:54:17
private static <E extends Comparable> void sort(E[] arr, int l, int r){
if (l >= r) return;
int mid = l + (r - l) / 2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
代码中的mid的计算公式为什么是 l + (r - l) / 2 ?
为什么不能是 (l+r)/2呢？
l和r从哪开始？l从索引为0的地方开始吗？r到len(arr)结束吗？
1回答
-
liuyubobobo
2023-06-01
1. 为什么使用 l + (r - l) / 2 ?
在这一小节的 08:22 位置开始，介绍了这一问题：https://class.imooc.com/lesson/1581#mid=36954
简单来说，使用 (l + r) / 2，由于中间的计算过程超过了 r，所以可能超过 r 所表示的数字的精度范围。比如 l 和 r 都是32 位有符号整型，如果 r = 2e9，l = 1e9 的时候，l + r = 3e9，超过了 int 的范围，造成溢出。但是 l + (r - l) / 2 没有这个问题。
==========
2.
第 10 行，初始调用的时候，l = 0, r = arr.length - 1
在 18 行和 19 行递归调用的过程，l 和 r 不断变化。
整个归并排序的过程， l 和 r 是怎么变化的，最终是如何完成对整个数组排序的，这是一个非常重要的问题。我在这一章课程前，详细就链表的递归做非常细致的解读，就是在为这里做准备。一旦你彻底理解了这个递归过程，今儿去理解课程后续其他的递归算法（非常多），就会容易很多。为了让大家更好地理解这一过程，这一章的 1-5 小节，我就是在把对链表的递归分析的过程，搬到归并排序中，让大家看到，递归过程的分析方式是完全一致的。
请再结合这一小节的内容，去理解在递归调用的过程中， l 和 r 是如何变化的，为什么会这么变化。（非常非常非常重要。）
https://class.imooc.com/lesson/1581#mid=36955
在这个基础上，6,7 两个小节我留了一个小作业，也是将链表中对递归调试跟踪的方式搬过来，以加深大家的理解：
https://class.imooc.com/lesson/1581#mid=36956
https://class.imooc.com/lesson/1581#mid=36957
请一定理解这一过程。非常非常非常重要。（比知道某一个具体的数据结构，比如要重要得多。）
继续加油！：）
0
相似问题