二分查找的一般方法

发表于   |   分类于   |  

​ 90%以上的程序员无法正确无误的写出二分查找代码 , 原来我对这句话一直不以为然，认为二分查找没什么大的难度，但后来发现在一些二分查找的求解上，我经常由于边界条件或者等号问题，导致结果不正确或者死循环，而这些细节问题恰恰是求职面试中，面试官想要考察的点。

​ 后来看到了知乎上一些人对二分查找的心得讨论https://www.zhihu.com/question/36132386,感觉自己之前对二分查找理解还不够深入。这其中有个比较重要的概念是“循环不变原理”，这个原理最早是在算法导论上的插入排序引入的，大致意思是这三点：

初始化：在循环的第一轮迭代前某个特性是正确的；

保持：如果在循环的某一次迭代开始之前某个特性是正确的，那么在下一次迭代开始之前，也是正确的；

终止：当循环结束，某个特性也是正确的。

这很像数学归纳法。下面举一个二分查找例子，查找一个有序数组中不超过值x的元素。写法可以有很多种

  • 写法1
1
2
3
4
5
6
7
8
9
10
11
int L = low;
int R = high + 1; 
int mid;
while(L + 1 < R) {//[L,R)
  mid = (L + R) / 2; 
  if(a[mid] <= x) {
      L = mid;
  } else {
   	  R = mid;
  }
}

​ 这个写法的意思可以用循环不变性原理解释：首先所求的区间是[L,R)，也就是说R是永远达不到的右端点，既然数组的index范围是low~high，那R的初值即为high+1,循环的终止条件是L+1=R，也就是区间仅剩一个元素（就是要求的元素），mid直接取(L + R) / 2，因为在循环内，L和R的差始终大于1，不需要再取上界者下界，mid的值始终介于L，R之间，既不可能等于L，也不可能等于R。

​ 当a[mid]<=x，也就是说要找的元素在右侧，mid也是符合要求的，所有L=mid。反之，要找的元素在左侧，但mid这个位置的元素是不满足要求的，正因为如此R＝mid，因为循环不变性条件就是取不到R，或者说右端点是不满足条件的。这样循环结束以后a[L]就是我们想要的元素了。

  • 写法2

这段代码直接从https://www.zhihu.com/question/36132386复制过来的。

1
2
3
4
5
6
7
8
9
10
int l = 0,r = n-1;	// x 必然存在于区间 [0,n-1] 内。(这里使用闭区间表示)
while( r-l+1 > 1 ) 	// 只要区间的长度大于1，就继续细分这个区间
{
    // 循环不变式 : x 在区间 [l,r] 内。
    int mid = (l+r+1)/2;	// 这里涉及到应该上取整还是下取整的问题
    if( x <= v[mid] )
        r = mid-1;	// x 在区间 [l,mid-1] 内
    else
        l = mid;		// x 在区间 [mid,r] 内
}

​ 这个循环不变保证区间长度大于1，最后循环结束以后，v[l]就是所求。但需要注意这里的mid值涉及到向上或者向下取整的问题，因为l和r的差有可能等于1，这会造成(l+r)/2等于l，那么如果此时x>v[mid], l=mid，那么l的值根本没变，区间也没变，这将会进入死循环。

​ 总体来说，我更倾向于第一种写法，虽然看起来没那么容易理解，但是理解以后写不容易错。当然以上两种方法也可以用来找大于等于x的最小元素，或者是直接查找某个x，稍做小的改动即可。