median-two-sorted-arrays-eg-sol

Input:
A = [1,3,5]
B = [4,7]

Assume 1-based indexing for simplification.

Step 1:
N = 3, M = 2, k = (3+2)/2 + 1 = 3
pa = 3/2 = 1, pb = 3-1 = 2
A[1] = 1 <= B[2] = 7
Continue search for k-pa = 3-1 = 2nd order statistic in A[2:] = [3,5] and B[:2] = [4,7].

Step 2:
A = [3,5], B = [4,7]
N = 2, M = 2, k = 2
pa = 2/2 = 1, pb = 2-1 = 1
A[1] = 3 <= B[1] = 4
Continue search for k-pa = 2-1 = 1st order statistic in A[2:] = [5] and B[:1] = [4].

Step 3:
A = [5], B = [4], k = 1
Since k == 1, return min(A[1], B[1]) = min(5,4) = 4.

4 is the median.