Find the median in an unsorted read-only array

user_11598035 0
Viewed 942

Given a read-only array with n elements, find the median (the ceiling(n/2)-th element by size) in the array, with O(logn) space and average time O(nlogn).

  • The elements in the array are different.
  • The array is not sorted.
  • You can't change any of the values in the array, only read them

I thought about using the idea of Quicksort but it is impossible to perform it without changing the array. And to copy to another array would exceed the required space.

space-complexity median time-complexity algorithm
2 Answers

You can solve it using divide and conquer approach, find a random element in between the minimum and maximum, check if it's median, if the median is lower or higher than it, and reduce the problem to a smaller size only on a subrange of the array.

  1. Set min as the smallest element in the array, and max as the biggest one.

  2. Choose a random number mid in range (min < mid < max), if there is no such mid, either min or max is median, find which and you are done.

  3. Check if either of min, mid or max is the median (linear search, count how many are bigger/smaller).

    3.1. If so,you are done.

    3.2. Otherwise, the median is in between (min,mid) or (mid,max), and you know where (if more are higher than mid or lower than it).

    3.3. If it's in (min,mid), set max = mid, otherwise, set min = mid.

    3.4. Return to 2.

Correctness:

  • If the algorithm finds a number - the stop clause is only due to finding the median.
  • For each iteration, the median is still in (min,max) (formal proof with induction..), and the range is guaranteed to shrink in each iteration, so the algorithm is guaranteed to stop and yield some result.

Time complexity:

  • Step 1: repeats only once and takes O(n) time.
  • Step 2: takes O(n) time (finding the distinct numbers in range) and repeats each iteration.
  • Step 3: takes O(n) time (going through each range is linear).

There are O(logn) iterations on average case (similar to binary search reasoning).

This gives us O(nlogn) time complexity

Space complexity:

Implementation dependent, but with tail recursion (similar to the above high level pseudo code) can actually be O(1). With regular recursion this is O(logn), for the stack.

user_5726700

Here is a simple algorithm. It consists of searching for the median by keeping track of the lower and upper bound of an interval where the median is.

Let E be the list of elements. Set the lower and upper bounds, L and U, of the median to null.

For every element e in E,

  1. If L is not null and e < L, e cannot be the median, skip to next element. If U is not null and e > U, e cannot be the median, skip to next element.
  2. Scan E and count the number B of elements before e, and the number A of elements after e.
  3. If A = B, e is the median, terminate. If A = B + 1, there is no single median, but e is immediately before the median point, terminate. If B = A + 1, there is no single median, but e is immediately after the median point, terminate.
  4. If A > B, the median is after e, set L = e. If B > A, the median is before e, set U = e.

Space complexity is O(1). Time complexity is at most O(n2) and O(nlogn) on average.

Example: 

E = [2 4 7 9 0 6 5]
       L,U = null,null  Initial state.
e = 2  L,U = 2,null     Update L.
e = 4  L,U = 4,null     Update L.
e = 7  L,U = 4,7        Update U.
e = 9  L,U = 4,7        Skip 9.
e = 0  L,U = 4,7        Skip 0.
e = 6  L,U = 4,6        Update U.
e = 5  Median is 5      Terminate.
user_38263870
Related