## 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