Middle - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

要点

中位数有两个

• 下位中位数：lowerMedian = (length - 2) / 2
• 上位中位数：upperMedian = length / 2

例：0, 1, 2, 3, 4, 5, 6, 7, 8, 9

• 下位中位数：(10 - 2) / 2 = 4
• 上位中位数：10 / 2 = 5

常用的是下位中位数，通用的写法如下，语言int经常自动向下取整，

median = (length - 1) / 2

指针的区间当然可以开区间，也可以闭区间，也可以半开半闭。但是老老实实两头取闭区间总是不会错。上面的中位数，转换成两头闭区间 [low, high] 就变成下面这样：

median = low + (high - low) / 2

这里还有个常见的坑，不要图快用加法，会溢出，

median = (low + high) / 2