```
class MedianFinder {
List<Integer> list;
public MedianFinder(){
list = new ArrayList<Integer>();
}
// Adds a number into the data structure.
public void addNum(int num) {
if(list.isEmpty()){
list.add(num);
return;
}
int index = findPlace(num,0,list.size()-1);
list.add(index,num);
}
// Returns the median of current data stream
public double findMedian() {
int mid = list.size() /2;
if(list.size() %2 == 0){
int num1 = list.get(mid);
int num2 = list.get(mid - 1);
return (double)(num1 + num2)/2.0;
}else{
return (double)list.get(mid);
}
}
int findPlace(int num, int beg, int end){
int mid = (beg + end)/2;
Integer midValue = list.get(mid);
if(num == midValue) return mid;
if(num < midValue){
Integer left = (mid == 0)? new Integer(Integer.MIN_VALUE): list.get(mid-1);
if(num >= left) return mid;
return findPlace(num,beg,mid-1);
}else{
Integer right = (mid == list.size() -1)? new Integer(Integer.MAX_VALUE): list.get(mid+1);
if(num <= right) return mid+1;
return findPlace(num,mid+1,end);
}
}
```

};

// Your MedianFinder object will be instantiated and called as such:

// MedianFinder mf = new MedianFinder();

// mf.addNum(1);

// mf.findMedian();