AmirWatad.com

Finding The Median Of Two Sorted Arrays

This is one of the beautiful cases where solving the general case first, and then applying it to a particular case is simpler and smoother than solving the particular case at once.

The problem:

Given two sorted arrays, “a” and “b”, with sizes “sa” and “sb” respectively, find the median of the union of these arrays.

Complexity requirements: O(log(sa + sb)) in the worst case, both time and space.

There are a few solutions for this problem, but non of them is as intuitive as the solution of a more general problem: The Select Problem:

Given two sorted arrays, “a” and “b”, with sizes “sa” and “sb” respectively, find the k-th smallest element of the union of these arrays. Under the same complexity requirements as above.

› Continue reading

Tags: Algorithms, Programming, Recursion