# 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) &lt; (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.