For people that could accept the build-in module solutions, there is also a module called `bisect`

that could do the jobs~, the complexity should be O(n) adding (*thanks @StefanPochmann's reminding) and O(1) finding the median

```
import bisect
class MedianFinder:
def __init__(self):
self.nums = []
def addNum(self, num):
bisect.insort(self.nums, num)
def findMedian(self):
nums = self.nums
if len(nums) % 2 == 0:
return (nums[len(nums)/2] + nums[len(nums)/2-1]) / 2.0
else:
return nums[len(nums)/2]
```