Design of an algorithm problems of Clog n[C++ code]

Question

Two sorted arrays of integers A[1..N] and B[1..N] are provided in ascending order.

Q:Design an O(log N)-time algorithm for finding out the median of all 2N integers. N may not power of 2.

To make thing easy, we can assume O(1) algorithm which return m such that:

2^m < N <  2^m+1

My problems:

1. N may not be power of 2, what does that mean? (understood)
2. I don't know how to change the input and make the length to power of 2 after found min and max elements from both array A and B.

Answer 1

You can solve this in O(logN) time using a binary search style approach. Consider the following two arrays:

1 1 2 2 3
1 2 3 4 5

Now the combined median is:

1 1 1 2 2 2 3 3 4 5 => 2

Let's see how we can find it. Start by guessing that the median is the center of each array:

1 1 2 2 3 => 2
1 2 3 4 5 => 3

Logically, we know the combined median can't possibly be less than 2 or greater than 3. Rather, it must be somewhere in between these two values. So we can discard everything in the first array smaller than 2 and everything in the second array larger than 3. This won't affect the position of the median because we are discarding an equal number of elements on both sides of where the combined median is. Conceptually, this leaves us with:

2 2 3 => 2
1 2 3 => 2

Now we already have an agreeing median, but the basic idea is to keep discarding half of the entries in each of the two arrays until we have a single median value.

This algorithm will perform as well as binary search, which is O(logN).