题目描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

知识点：

  • 二分搜索

解题思路：

  • 这道题分为两部分，一部分是将所给的数按照从小到大的顺序插入到数组中，方便后序中位数的查找。一部分是在我们上一步所创建的数组中找到其中的中位数。
  • 首先是第一部分，我们采取二分搜索的方法来插入中位数，如果中间值等于所给值那么我们将所给值插入到中间值的旁边便好，这属于特殊情况。其余按照二分搜索来进行便好。
  • 第二部分是查找中位数，如果数组为奇数那么我们按照中间的索引输出便好，如果是偶数，我们需要输出中间两个数的和的一半便好

解题代码：

  1. let arr = [];
  2. function Insert(num) // 二分搜索查找中位数
  3. {
  4.     // write code here
  5.     if(!arr.length) {
  6.         arr.push(num);
  7.         return;
  8.     }
  9.     let left = 0;
  10.     let right = arr.length - 1;
  11.     while(left < right) {
  12.         let mid = (left + right) >> 1;
  13.         if(arr[mid] === num) {
  14.             arr.splice(mid+1,0,num);
  15.             return;
  16.         }else if(arr[mid] < num) {
  17.             left = mid + 1;
  18.         }else {
  19.             right = mid - 1;
  20.         }
  21.     }
  22.     return arr.splice(right,0,num);
  23. }
  24. function GetMedian(){
  25.     // write code here
  26.     if(!arr.length) return null;
  27.     let length = arr.length;
  28.     let mid = (length - 1) >> 1; // 中间值的索引，或者中间值靠右的索引
  29.     if(length % 2 === 1) { // 判断数组的长度是奇数还是偶数
  30.         return arr[mid];
  31.     }else {
  32.         return (arr[mid] + arr[mid+1])/2;
  33.     }
  34. }