二分法binary search 模板

二分法模板：
二分法的主要特点：
（1） 每次都要砍一半（所以很快）时间复杂度是O(logN)
（2）如果array 是没有排序的，那首先必须得排序，二分法是基于排序的基础上来做的。

需要注意的特点：
（1）异常值处理：数组的长度为0，target value 分别在第一位和末尾找到。
（2）注意start+1< end 防止死循环
 （3）mid = start + (end-start)/2

Both your formulas will overflow, but under different circumstances:

• The (start+end) part of your (start+end)/2 formula will overflow when start and end are both close to the integer limit on the same side of the range (i.e. both positive or both negative).
• The (end-start) part of your start+(end-start)/2 formula will overflow when start is positive and end is negative, and both values are close to the respective ends of the representable integer values.

There are no "generic" rules, you do it case-by-case: look at parts of your formula, think of situations that could cause overflow, and come up with ways to avoid it. For example, the start+(end-start)/2 formula can be shown to avoid overflow when you average values with the same sign.

This is the hard way; the easy way is to use higher-capacity representations for intermediate results. For example, if you use long longinstead of int to do intermediate calculations and copy the results back to int only when you are done, you will avoid overflow assuming that the end result fits in an int.

int binarySearch(vector<int> &A, int target) {
        //如果Array的size是0直接return -1
if (A.size() == 0) {
            return -1;
        }
       
//赋值
        int start = 0;
        int end = A.size() - 1;
        int mid;

        while (start + 1 < end) { //注意点一： 防止死循环          
            mid = start + (end - start) / 2; //注意点二：防止溢出， 如果使用 [(end+start)/2]，如果size 是10的话，5+7=12> 10 中值数就会大于原有的规定，所以就会溢出。 这种方法
                                //是会防止溢出
            if (A[mid] == target) {
                end = mid;
            } else if (A[mid] < target) {
                start = mid;
            } else if (A[mid] > target) {
                end = mid;
            }
        }
     
//如果一开始就相等，就直接return
        if (A[start] == target) {
            return start;
        } //先判断开始和最后一位是否相等，特殊值处理。
        if (A[end] == target) {
            return end;
        }

        return -1;
    }
};

一些题目的变体：
1. Search for a Range:
http://lintcode.com/en/problem/search-for-a-range/

用二分法模板：可以在初次二分法之后，

（1）先向左边找期初值
（2）再像右边找最后的一个值。

2. Search in a sorted matrix:
使用两次binary search 方式，先对列进行搜索再对行进行搜索。

3. Search in a sorted matrix II:
 http://lintcode.com/en/problem/search-a-2d-matrix-ii/

和sorted matrix 不一样的地方：