How to find the Median algorithms

I had a super cool exercise on Hackerank contest, I wouldn’t explain the whole exercise but only the part of finding the median of an unsorted listed of numbers.

In retrospective there are several ways for calculating this simple value, but for this exercise we had to recalculate it each time when only changing one number each time, and the N was very big, so the regular way couldn’t cut it.

example code {#examplecode}

data = [5,1,3,2,9,7...,n]  

Here is the simple regular way: {#hereisthesimpleregularway}

data.sort()  
length = len(data)

if length%2 == 0:  
    answer = (data[length/2]+data[length/2-1])/2
else:  
    answer = data[math.floor(length/2)]

Select algorithm {#selectalgorithm}

I wouldn’t post the select algorithm code here is it is not relevant here (you can read here)

The bottom line is simple checking if even or odd length and the getting the K number and if it is even the k-1 and then do the same as you done above.

The solution {#thesolution}

This solution is not the “go to” as it is quite specific for our exercise, when you need to recalculate the median several times by changing only one number on big unordered lists.

You will run through the list and count each number counts.

ie:

data = [5,1,3,2,9,7,1,1,3]

//means

counts = {  
    1: 3,
    2: 1,
    3: 2,
    5: 1,
    7: 1,
    9: 1
}

and to calculate the median is simply counting to the middle from the bottom up.

ie:

1,1,1,2,3,3,5,7,9

so now when I add another number or remove one, I simple update my counts objects and recounts to the middle again to find the median.