前xia言che

今天是2018年3月4号，马上就春招了，不对，准确的说是春招已经开始了，简历还没有投，最近在赶一个项目，想把它写到上面，目前简历的开发经验还是空白。虽然三年下来课设没少做，代码也没少敲（大概5w行左右，其实代码量还是远远不够的）；虽然课设大多都是优秀（其实做的真的菜），所以导致今天这个尴尬的局面。今天刷剑指offer时看到二分的题目，也是困扰本ACMer（实则菜的抠脚的那种）多年的二分边界问题终于想解决下，所以google一番后，发现貌似也没有想象的那么难，所以忙里偷闲的来总结下。下面开始正文。

边界问题

确定边界取决于变量的初始状态，可以分为左闭右开和左闭右闭两种写法。

左闭右开

我比较喜欢这种，没有理由，就是喜欢。先看一个例子：

int search1(int array[], int n, int v)
{
    int left, right, middle;
    left = 0, right = n;    //!!!!
    while (left < right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
            right = middle;    //！！！！
        else if (array[middle] < v)
            left = middle + 1;    //！！！！
        else
            return middle;
    }
    return -1;
}

看感叹号注释那行，初始上下边界是[0,n)，典型左闭右开的初始化，所以while的条件就有了吧。其次看第二个感叹号的位置，如果中间位置的元素大于要找的元素，那么该元素在前半段。记住我们用的是左闭右开，所以应该把上边界定为middle，如果这里不小心写成right = middle - 1;那么如果此时的middle-1位置就是要找的元素，那么你就成功的避开了它。最后看第三个感叹号位置，确定下边界，如果中间位置元素小于要找的元素，那么它肯定在后半段，既然小于了，当然要left = middle +1;

左闭右闭

然后看下左闭右闭的写法：

int search2(int array[], int n, int v)
{
    int left, right, middle;
    left = 0, right = n - 1;   //!!!
    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
            right = middle - 1;    //!!!
        else if (array[middle] < v)
            left = middle + 1;   //!!!
        else
            return middle;
    }
    return -1;
}

同样看第一个感叹号，初始化为[0,n-1]，所以用左闭右闭，所以while循环就有了；第二个感叹号，既然中间位置大于要找的元素所以上边界直接定为它的前一个也无妨；第三个感叹号，中间位置小于要找的元素，下边界定位它的后一个。

就按照这个套路，根本不会出错！

溢出问题

其实这个问题一般不会出现，但是在比赛时就不好说了（谁知道有多么严bian谨tai的测试数据），但是干码农这行，严谨点没毛病。注意在确定中间位置时，我们写的是middle = (left + right)/2;如果left+right超出定义的数据类型的最大值就会出错。所以这里最好应该写成：middle = left + (right - left)/2;。
还有一个就是这里的除以2，让计算机做除法其实是比较慢的，所以可以优化为二进制的移位：middle = left + ((right - left)>>1);。这样就完美多了。

参考资料：
blog

题目链接：
VJ