以前写Binary Search边界条件总是不好把握，看到有同学用九章的模板，没觉着怎么好用，后来听了九章的课之后，才发现，这个模板好神奇。
模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int findPosition(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    int start = 0;
    int end = A.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] == target) {
            return mid;
        } else if (A[mid] > target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }
    return -1;
}

几个关键点：

  1. start + 1 < end
  2. start + (end - start) / 2，可以避免(start + end) / 2, 可能造成的溢出
  3. A[mid] ==, <, >，三种情况先分开考虑，写完后也许可以合并. 范围缩小要用 start = mid 或 end = mid
  4. A[start] A[end] ? target, 当循环结束的时候，并不能确定start, end到底哪个是所求解，要分别判断

两类二分法

  1. 二分位置 Binary Search on index
  2. 二分答案 Binary Search on result

理解二分法的三个层次

  1. 头尾指针，取中点，判断往哪走
  2. 寻找满足某个条件的第一个或是最后一个位置
  3. 保留剩下来一定有解的那一半