Sushil Chaskar Sushil Chaskar - 1 month ago 7
Python Question

Error in getting the running median

I am trying to get a running median for a number of integers. For example: 6 elements will come one by one, let say 12,4,5,3,8,7 for which running median at each input is 12,8,5,4.5,6,5 respectively. I wrote a python code but it seems to give incorrect answer. Help is appreciated .

n = int(raw_input().strip())
s=[]
for i in xrange(n):
a=int(raw_input())
if len(s)==0:
s.append(a)
print "%.1f" % a
else:
for j in xrange(len(s)):
if a<s[j]:
s.insert(j,a)
if a>=s[-1]:
s.append(a)
if len(s)%2==0:
print "%.1f" % float((s[len(s)/2] + s[len(s)/2 -1])/2.0)
else:
print "%.1f" % s[len(s)/2]

Answer

Read the comments embedded in the code below -

n = int(raw_input().strip())
s=[]
for i in xrange(n):
    a=int(raw_input())
    if len(s)==0:
        s.append(a)
        print "%.1f" % a
    else:
        for j in xrange(len(s)):
            if a<s[j]:
                s.insert(j,a)
                break  # break after insertion to avoid multiple insertions
        else:  # Read https://docs.python.org/3/reference/compound_stmts.html#for
            s.append(a)

        if len(s)%2==0:
            print "%.1f" % float((s[len(s)/2] + s[len(s)/2 -1])/2.0)
        else:
            print  "%.1f" % s[len(s)/2]