二分查找的理解

常见的二分模板：

模板一，区间是左闭右闭的，即查找区间是[l,r]

int binary_search(int l, int r, int a[], int x)  //返回值是元素x在数组a中的位置（下标）
{
    int mid = 0;
    while(l <= r)
    {
        mid = (l+r) >> 1;
        if(a[mid] == x)
            return mid;
        if(a[mid] < x)
            l = mid+1;
        else
            r = mid-1;
    }
    return -1;
}

模板二，区间是左闭右开的，即查找区间是[l,r),老外喜欢玩这个，然后整个STL基本都是这种左闭右开的。

int binary_search(int l, int r, int a[], int x)
{
    int mid = 0;
    while(l < r)
    {
        mid = (l+r) >> 1;
        if(a[mid] == x)
            return mid;
        if(a[mid] < x)
            l = mid+1;
        else
            r = mid ;
    }
    return -1;
}

注意这两个模板的区别，如果是左闭右闭的，while循环处应该是可以l == r的，然后在更新r的时候要将r赋值为mid-1，因为查找子区间也应该是左闭右闭的区间（因为mid在本次查找的时候已经查过了，所以子区间划分的时候mid不应该在区间中）。

如果是左闭右开的模板，则在更新的时候r要赋值为mid，这样才能保证查找子区间的时候也是左闭右开的。

l更新的时候始终是mid+1，毕竟两个模板都是左闭区间。