Something must know about Median

• odd: median of {3, 3, 5, 9, 11} is 5
• even: the median of {3, 5, 7, 9} is (5 + 7) / 2 = 6

Kth of two sorted array in O(log(m + n))

O(m + n)

Acting like Merge Sorted Array, just take first k elements.

But, I will show you a brute force version, because it can be optimized to O(log(m + n)) easily.

O(m + n) Brute Force

search through kth of Array M and Array N

Code is like

foreach n in array m and array n

if isKth(n)
found

Core tech is how to determine if n is the kth.

isKth

Imagine that take k elements from Array M and Array N, m elements from Array M and n from Array N.

such that, the Kth element must be MAX(mth of Array M, nth of Array N)

e.g.

Array M [1, 3, 5, 7, 9]
Array N [0, 2, 4, 6, 8]

Array M [1,  3,  5,  7,  9]
^
|
+-+
|
Array N [0,  2,  4,  6,  8]

try to put the nth element after the mth element
• take 3 elements from M: [1, 3, 5]
• take 4(7-3) elements from N: [0, 2, 4, 6]
• the 7th element is: MAX(5,6)
• 8th..10th [7, 8, 9] are greater than or equals to the 7th

that is

• k = m + n
• kth = MAX(ArrayM[m], ArrayN[n])
• elements in ArrayM[m + 1..end] and ArrayN[n + 1..end] must be greater than or equals to the kth

So checking kth code is like

function isKth(m, ArrayM, ArrayN)
n = k - m

return ArrayN[n] <= ArrayM[m] <= ArrayN[n + 1]

O(log(m + n)) Binary Search

with isKth, we can write a binary search version using binary search template.

search arrayM

while s < e

m = (s + e) / 2

if iskth(m, arrayM, arrayN)
return ArrayM[mid]

// solve this later
s = m + 1 or e = m

this will take O(log(m)) time, if kth is not found, do the same to ArrayN.

s = m + 1 or e = m

when mid is not kth, we are going to remove half of the elements that must not contain the kth.

searching Array M

Array M [0, 2, 4, 6, 8]
s     m     e

Array N [1, 3, 5, 7, 9]
n
k = 7
n = k - m
• ArrayM[m] = 4
• ArrayN[n] = 7

If ArrayM[m] is not the kth, that is, ArrayM[m] is less than ArrayN[n] or ArrayN[n + 1].

When ArrayM[m] < ArrayM[n], we must enlarge the ArrayM[m], so s = m + 1 if we want ArrayM[m] to be the kth.

Similarly, we must diminish ArrayM[m] if ArrayM[m] > ArrayM[n]

In code:

if ArrayM[m] < ArrayM[n]
// enlarge ArrayM[m]
s = m + 1
else
// diminish ArrayM[m]
e = m

Put them together

len = len(A) + len(B)

if len is odd
kth(A,B, len/2)
else
(kth(A,B, len/2) + kth(A,B, len/2 + 1)) / 2

Note

• Array in my code start from 0
• Sometimes, no element on any index, just treat it as -INFINITE