Binary Search

什么时候使用二分法？

当题目要求O(logn)复杂度的时候，99%都是二分法。他比线性算法还要快。

当题目要求find any/first/last position of target，可以考虑二分法。

当然，二分法需要在sorted array上进行，如果array本身无序，可以考虑排序他，但是复杂度不再是O(logn)。

二分法有三个境界：

    1. 头尾指针取重点，判断往哪走
    2. 找满足条件的第一个或者最后一个位置
    3. 去掉一半没有解的答案

二分法的通用模板：

    1. start + 1 < end
    2. start + (end - start) / 2
    3. A[mid] ==, <, >
    4. A[start], A[end], target?