浅谈二分

二分查找在程序设计中，是一个十分基础并且易错的功能。

第一个真正正确的二分查找算法，在第一个二分查找实现后的12年，才被发表出来。——《CSAPP》

很久没有写代码了，最近一直在看《编译原理》，《TCP/IP详解卷1：协议》，今天写了写代码，发现代码能力下降的非常厉害，厉害的可怕……二分写的时候多拙计了半天。

于是写此文予以总结。

二分的边界问题

在下认为，二分最难的问题是边界问题，只要掌握好边界问题，即可有效避免可能的错误情况。

所谓的错误情况或者繁琐的情况，就是：

二分结束的边界情况？( l <= r ? l < r ? l < r - 1 ....)
二分时候的变化？( r = mid - 1 ? r = mid + 1 ? l = mid ....)

其次需要注意的问题，其实就是可能出现的上下取整问题。如 l = 3 , r = 4，正确答案位于 4 的时候的转移情况。

所谓的边界问题，就是指：“要保证，二分的两端区间开闭情况，自始至终要保持一致。“（没错，这是我说的。）

也就是说，要保证在二分的过程中，正确答案所在的位置，时刻满足于l,r的区间关系。比如，正确答案时刻存在于[l,r]或时刻存在于[l,r)等等……

全闭区间

感觉最好理解的二分，就是这种全闭区间的二分。

int low = st , high = ed , mid = ( l + r ) / 2 ;
while( low <= high )
{
    if( a[mid] > target )
      r = mid ;
  	else if( a[mid] < target )
      l = mid ;
  	else 
      return mid; // mid is the answer.
    mid = ( l + r ) / 2 ;
}

在二分过程中，时刻保证答案是在[low,high]中的。这样，很明显便可写出二分的结束条件和转移条件。

当然，需要注意的是如果只有前两个if条件，很容易导致死循环难以跳出，所以我们还需要对mid进行一下判断。

左闭右开区间

曾经在下写的

这是我以前一直倾向于写的一种二分，因为我感觉它和STL库等的区间表示维持了一个统一。

int low = st , high = ed , mid = (l + r + 1 ) / 2;
while( low < high )
{
    if( a[mid] > target )
      r = mid - 1 ;
    else 
      l = mid ;
    mid = ( l + r + 1 ) / 2;
}

这种写法，以前觉得很好。但是现在发现，一方面mid的转移和r的转移不够直白，过一段时间很容易记混。而且，对于在 leetcode 上刷题的时候，经常需要在 while 结束后再做处理，感觉比较头疼。

所以不是很适合写。

下面我将尝试对这段代码的实现思路进行推导：

int low = st , high = ed , mid = ( l + r ) / 2;
while( low < high )
{
    if( a[mid] > target )
      r = mid - 1 ;
    else 
      l = mid ;
  	mid = ( l + r ) / 2;
}

为了保证左闭右开，显然我们需要high= mid - 1，这样才能保证正确答案的左闭又开。

同样，为了保证左闭右开，我们必须while( low < high ) 作为结束条件（其实不是很必须，其他等价表达也不是不行）。

只有这样，当最终 [low,high),且 low = high 时，答案才呼之欲出，就是low。

但是这样的写法会有一个问题，问题主要在，当low = 3 , high = 4而正确答案是 4 的时候。这样写，low永远也不会等于4 。然而high,low我们刚刚都已经推导完毕了。

那么，只能想办法从 mid入手，要解决这样的办法很简单~想办法让 mid在low = 3,high=4的情况下，落到4不就完事了嘛？

所以，我们有mid = ( l + r + 1 ) / 2，向上取整。

队友的写法

队友今天看到我二分卡住，无情的教育了我。

队友主要写法是：

int low = st , high = ed , mid = ( l + r ) / 2 ;
while( low < high - 1 )
{
    if( a[mid] <= target )
      low = mid ;
  	else
      high = mid ;
   	mid = ( l + r ) / 2 ;
}

队友的写法，和我上面你的写法很像，都是在解决同样的问题。既然low = 3 , high = 4 的时候会出现问题，那我不让这种情况出现不就好咯？

于是，我们有了 low < high - 1，这样保证，low和high中间隔了一个mid，而这个间隔的mid，也能保证答案一定能落在low上（因为low那里是小于等于）。

当答案落在low上后，low和high之间相隔1，不满足循环条件，自然也就结束循环了。

碎碎念

(l+r) / 2 在有些情况有溢出的风险，所以可以考虑使用l + ( r - l ) / 2