剑指 Offer 41. 数据流中的中位数（困难）

题目：

class MedianFinder {      //暴力解法：每添加一个数字后用sort进行排序，然后返回中位数，时间复杂度：nlogn，会超时。因此采用**二分法查找并进行插入的方法**。时间复杂度：logn
public:
    vector<int> nums;      //初始化一个当前数组
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(nums.empty()){
            nums.push_back(num);      //当前数组为空则直接插入数字
        }
        else{
            nums.insert(lower_bound(nums.begin(), nums.end(), num), num);      //当前数组不为空：利用lower_bound()，在nums.begin()和nums.end()中的前闭后开区间进行二分查找，返回大于或等于num的第一个元素位置。然后在该位
        }                                                                                                                                                                                            //置插入num
    }
    
    double findMedian() {
        int n = nums.size();
        return n%2==1 ? nums[n/2] : (nums[n/2-1]+nums[n/2])*0.5;      //按要求返回中位数。要注意的是如果数组为偶数的话，返回中间两个数的平均数时要用*0.5，不能用/2，否则小数部分会被省略
    }
};

作者：腐烂的橘子
链接：https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solutions/104353/you-xian-dui-lie-by-z1m/
来源：力扣（LeetCode）