Binary search based solution
\nclass MedianFinder {\n    ArrayList<Integer> nums;\n\n    public int findInsertIndex(int target) {\n        int low = 0;\n        int high = nums.size() - 1;\
```\nclass MedianFinder {\n    ArrayList<Integer> nums;\n\n    public int findInsertIndex(int target) {\n        int low = 0;\n        int high = nums.size() - 1;\n\n        while (low <= high) {\n            int mid = (low + high) / 2;\n\n            if (nums.get(mid) >= target)\n                high = mid - 1;\n            else\n                low = mid + 1;\n        }\n\n        return low;\n    }\n\n    /**\n     * initialize your data structure here.\n     */\n    public MedianFinder() {\n        nums = new ArrayList<>();\n    }\n\n    public void addNum(int num) {\n        if (nums.size() == 0) {\n            nums.add(num);\n        } else {\n            int index = findInsertIndex(num);\n            if (index == nums.size()) {\n                nums.add(num);\n            } else {\n                nums.add(index, num);\n            }\n        }\n    }\n\n    public double findMedian() {\n        int mid = (nums.size() - 1) / 2;\n        return nums.size() % 2 == 0 ? (nums.get(mid) + nums.get(mid + 1)) / 2.0 : nums.get(mid);\n    }\n}\n\n```
['Binary Tree', 'Java']