How to find the median of two sorted arrays in JavaScript

JavaScript, algorithms, arrays

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);
}