Advanced Binary Search

这类型的Binary Search 是真正熟悉算法之后方能想出来的。把结果集想清楚，而且是可以通过不断shrink一半结果集得到结果。

Minimum Size Subarray Sum：

1. 直观能想到用subSum
2. 如何定位哪两点的subArray是满足条件的，固定一定，用binary Search查找另外一点，O(nlogn)，因为subSum这个数组是一个有序递增的数组。
3. 用two pointer，window 夹逼。与前者目的相同，实现方法不同。

Copy book

通常这类型题目可以有其他的解法：

• DP
• 二分法（好难想）
  • 为什么要从最大值开始？
  • copier = total / subSum

public int copyBooks(int[] pages, int k) {
   if (pages.length == 0) return 0;
   int total = 0, max = pages[0];

   for (int i = 0; i < pages.length; i++) {
       total+= pages[i];
       max = Math.max(max, pages[i]);
   }

   int l = max, r = total;
   while (l < r) {
       int mid = l + (r - l) / 2;
       if (countCopiers(pages, mid) > k) l = mid + 1;
       else r = mid;
   }
   return l;
}
private int countCopiers(int[] pages, int limit) {
    if (pages.length == 0) return 0;

    int copiers = 1, sum = pages[0];
    for (int i = 1; i < pages.length; i++) {
        if (sum + pages[i] > limit) {
            copiers++;
            sum = 0;
        }
        sum += pages[i];
    }
    return copiers;
}

Wood Cut

Find the Duplicate Number

Solution：

• Pigeonhole principle（加强版二分法）

  1. 二分法主要的思想是，当前集 --> 结果集 的过程中可以把一半结果一定不在当中情况删除，从而进一步把范围缩小一半达到O(logN)的情况
  2. 用下标来表示整个数组的数字！
     • 我们比较的mid而不是nums[mid]
     • 因为mid是下标，所以判断式应为cnt > mid，最后返回min
  3. 从中间任意找一点分开之后，按照pigeonhole Principle /pi'geon/ ，我们需要遍历其中一半，count 有多少个数字小于等于中间数字。如果总数大于中间数字判断重复结果应该是在左，反则在右。

public int findDuplicate(int[] nums) {
    int min = 0, max = nums.length - 1;
    while(min <= max){
        // 找到中间那个数
        int mid = min + (max - min) / 2;
        int cnt = 0;
        // 计算总数组中有多少个数小于等于中间数
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= mid){
                cnt++;
            }
        }
        // 如果小于等于中间数的数量大于中间数，说明前半部分必有重复
        if(cnt > mid){
            max = mid - 1;
        // 否则后半部分必有重复
        } else {
            min = mid + 1;
        }
    }
    return min;
}

Kth Smallest Element in a Sorted Matrix

1. Heap
2. 二维矩阵查找相似，每次都拿缩小范围后的一个值来尝试是否满足条件，逐渐逼近答案，跟很多题目类似：wood cut, Duplicate Number, pow()

Search a 2D Matrix II：

1. O(m + n) ：从右上角开始，直到找到target

   1. 如果当前值比target小的话向下移动
   2. 如果当前值比target大的话向左移动

2. 另外的解法，时间复杂度要好好考虑，比较复杂

Kth Smallest Element in a BST