[LeetCode] 295. Find Median from Data Stream

 Problem : https://leetcode.com/problems/find-median-from-data-stream/

Use insert sort to keep the data cache in ascending order.

Then median = ( nums[len(nums) // 2 ] + nums[(len(nums) - 1) // 2] ) / 2

Time Complexity = O ( Log N ) +  O ( N ) ≈ O ( N )

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []
        

    def addNum(self, num: int) -> None:
        
        def lowerBoundary(n):
            left, right = 0, len(self.nums)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if self.nums[mid] == n:
                    right = mid
                elif self.nums[mid] < n:
                    left = mid + 1
                elif self.nums[mid] > n:
                    right = mid
            
            return left if left - 1 >= 0 else 0
            
        # insert sort   
        self.nums.insert(lowerBoundary(num), num)
        

    def findMedian(self) -> float:
        
        l = len(self.nums)
        
        return (self.nums[l//2] + self.nums[(l-1)//2]) / 2.0
        


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()