challenge-median/index.js at master · wrthwhl/challenge-median · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
'use strict';

function findMedian (arr1, arr2) {

  if (!arr1 || !arr1.length || !arr2 || !arr2.length || arr1.length !== arr2.length) return false;

  if (arr1.length === 2 && arr2.length === 2) {
    return (Math.max(arr1[0], arr2[0]) + Math.min(arr1[1], arr2[1])) / 2;
  }

  const m1 = median(arr1);
  const m2 = median(arr2);

  if (!m1 || !m2) return false;

  if (m1 === m2) {
    return m1;
  }

  if (m1 > m2) {
    const m1Slice = arr1.slice(0, Math.floor(arr1.length/2) + 1);
    const m2Slice = arr2.slice(arr2.indexOf(m2), arr2.length);
    return findMedian(m1Slice, m2Slice);
  }

  if (m2 > m1) {
    const m1Slice = arr1.slice(arr1.indexOf(m1), arr1.length);
    const m2Slice = arr2.slice(0, Math.floor(arr2.length/2) + 1);
    return findMedian(m1Slice, m2Slice);
  }
}

// util
function median (values) {

  values.sort( function (a,b) {return a - b;} );

  const half = Math.floor(values.length/2);
  let median;

  if (values.length % 2)
    median = values[half];
  else {
    median = (values[half-1] + values[half]) / 2.0;
  }

  return typeof median === 'number' ? median : false;

}

exports.findMedian = findMedian;