题解 | JAVA #数据流中的中位数# [P0]

Insert通过binarySearch寻找插入位.

将一个数x插入一个有序数组中，
插入位置就是标准二分查找(不论左闭右开还是左闭右闭)的最终左下标“l”。

多加一嘴留着自己复习:
二分查找提前输出或不提前输出不影响排序结果，但影响有duplicate情况下的插入位置
不提前输出(不论左闭右开还是左闭右闭)，插入位pos is the index of the first 
element greater than the key, (i.e. insertion-point of Collections.binarySearch).
不提前输出就是指没有"if(arr[mid] == target) return mid;"这句。

if ("Condition-A") // e.g. arr.get(mid) <= target
  lo = mid + 1;
else
  hi = mid;    // 左闭右开
  hi = mid - 1 // 左闭右闭

用以上逻辑，停止时
 lo：first elem doesn't meet "Condition-A", 
     e.g. first element greater than target
 hi(左闭右开): 等于lo
 hi(左闭右闭): 等于lo-1, last elem meets "Condition-A"
     e.g. last element less-or-equal to target

import java.util.*;

public class Solution {
  List<Integer> arr = new ArrayList<Integer>();

  public void Insert(Integer num) {
    int pos = searchInsertPos(num);
    // 偷懒就用library
    // int a = Collections.binarySearch(arr, num);
    // int pos = a >= 0 ? a : -a-1;
    arr.add(pos, num);
  }

  public Double GetMedian() {
    int size = arr.size();
    if ((size & 1) == 1)  // odd
      return new Double(arr.get(size/2));
    else // even
      return (arr.get(size/2 - 1) + arr.get(size/2)) / 2.0;
  }
  
  // 就是最普通的左闭右开的binarySearch
  public int searchInsertPos(Integer target) {
    int l = 0, r = arr.size();
    while (l < r) {
      int m = l + ((r-l) >> 1);
      if (arr.get(m) <= target)
        l = m + 1;
      else
        r = m;
    }
    return l;
  }
}