#
Median of Two Sorted Arrays

11 Dec 2011

```
Given 2 sorted arrays, n and m in length, find the median.
```

First, let's just assume that the numbers are unique and `(n+m)`

is odd.

The first obvious solution that comes to me takes `O(n)`

.

We use 2 pointers starting on the beginning of each array. We walk them one at a time in increasing order. If we have walk `(n+m)/2`

times, then the latest touched element is the median.

Anyway, on Leetcode.com, it states that the solution should take only `O(log(m+n))`

.

Ok…. `O(log(m+n))`

requires some sort of binary search.

Anyway, let's make some random observations as I always do.

### Observation 1

If we combine the two arrays and keep the order, the median is at the `((n+m+1)/2)th`

.

### Observation 2

Let's throw out some examples:

```
1 3 5 7 9 11 13
2 4 6 8 10 12
1 2 3 4 5 6 7
8 9 10 11 12 13
1 2 3 4 7 8 9
5 6 10 11 12 13
```

What we can do with `O(log n)`

is to pick one element in the first array and find the lesser elements in the second array.

### Observation 3

Let's say we pick the element `x-th`

from the first array. We only need to consider the first `(((n+m)/2) - x)`

elements in the second array.

This observation is something. We pick the element `i-th`

in the first array, say `a[i]`

, and we find all the lesser elements in the second array. Let's say `b[j]`

is the biggest element that is less than `a[i]`

.

- if
`(i+j) == (n+m)/2`

, then we got the answer.
- if
`(i+j) > (n+m)/2`

, then we try again with the `(i/2)-th`

element.
- If
`(i+j) < (n+m)/2`

, then we try again with the `(i + (n-i)/2)-th`

element.

You know, the binary search algorithm. You need to refine the algorithm, a little.