# Python's bisect module, O(n) add and O(1) return median

• 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 = []

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]``````

• No, `bisect.insort` isn't O(log n) but only O(n). The documentation even reminds you of it:

"Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step."

• ha, so embarrassed XD Thanks for reminding!

• Well, you're probably by far not the first who made that mistake :-P

Btw, an alternative way to compute the median:

``````def findMedian(self):
nums = self.nums
n = len(nums) / 2
return (nums[n] + nums[~n]) / 2.
``````

• oh damnnn, I forget the beautiful ~n trick!! nice!

• Hahahaha, guess what... for the OJ test suite, your solution is, despite the bad complexity class, the fastest Python solution posted so far :-). Even though the OJ test suite does have a case with n > 20000.

• haha cool, totally unexpectedlyXD

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.