10107 - What is the Median?

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers. Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}. If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4 !

Input

The input file consists of series of integers X (0 ≤ X < 2 ^31) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.

Output

For each input print the current value of the median.

Sample Input

1 3 4 60 70 50 2

Sample Output

1 2 3 3 4 27 4

Solution 1

hint : Insertion Sort + Binary Search

from sys import stdin, stdout


def binary_search(n, key):
    low = 0
    high = n - 1
    while low < high:
        middle = (low + high) // 2
        if lst[middle] <= key:
            low = middle + 1
        else:
            high = middle
    return low


lines = stdin.readlines()
lst = []
size = 0
ans = ''
for s in lines:
    num = int(s)
    size += 1
    idx = binary_search(size, num)
    lst.insert(idx, num)
    mid = size // 2
    if size % 2:
        ans += str(lst[mid])
    else:
        ans += str((lst[mid] + lst[mid - 1]) // 2)
    ans += '\n'
stdout.write(ans)

Solution 2

hint : max-heap + min-heap

from sys import stdin, stdout
import heapq

lines = stdin.readlines()
max_heap = []
min_heap = []
is_odd = False
ans = ''
for s in lines:
    num = int(s)
    is_odd = not is_odd
    if is_odd:
        heapq.heappush(min_heap, num)
    else:
        heapq.heappush(max_heap, -num)
    if min_heap and max_heap:
        while min_heap[0] < -max_heap[0]:
            tmp = heapq.heapreplace(min_heap, -max_heap[0])
            heapq.heapreplace(max_heap, -tmp)
    if is_odd:
        ans += str(min_heap[0])
    else:
        ans += str((-max_heap[0] + min_heap[0]) // 2)
    ans += '\n'
stdout.write(ans)

[Uva]10107 - What is the Median?

A fun problem.