How to find the median of two sorted arrays in JavaScript

Here is one means of finding the median of two sorted arrays A and B with sizes m and n respectively.

findMedianTry in REPL
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
function findMedian(A, B) {
const m = A.length;
const n = B.length;
if ((m+n) % 2) return findKth(A, B, parseInt((m+n) / 2), 0, m - 1, 0, n -1); // odd
return ( // even
findKth(A, B, parseInt((m+n)/2)) +
findKth(A, B, parseInt((m+n)/2) - 1)
) / 2
}
function findKth(A, B, k,
aStart = 0, aEnd = A.length - 1, bStart = 0, bEnd = B.length - 1) {
const aLen = aEnd - aStart + 1;
const bLen = bEnd - bStart + 1;
if (aLen === 0)
return B[bStart + k];
if (bLen === 0)
return A[aStart + k];
if (k === 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
let aMid = parseInt(aLen * k / (aLen + bLen));
let bMid = parseInt(k - aMid - 1);
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}