二分查找应该算是比较基本的算法了,但考虑到各种边界问题,真正能把二分查找写对的人不多。

一些模板

在阅读此博客之前,如果您还没有接触过二分查找,可以看看这个

二分的模板有好几套,我在这里分享一下,并说明用法。

整数二分:

第一套模板是我见的最多的,适用场景:我们要查找的内容并不满足一个区间,而是一个点,就比如说在有序数组中查找值时,就适合用此模板:

while(l <= r) {
        mid = l + r >> 1;
        if(check(mid) > key) {  
            r = mid - 1;
        } else if(check(mid) < key) {
            l = mid + 1;
        } else {
            return mid;   //找到了就返回mid
            break;
        }
    }
return -1;    //否则返回-1

当然,第一个模板是完全可以被后两个取代的

第二套模板适合答案在一个区间内,而我们要求出满足题意的第一个元素,也就是大于等于key的第一个元素

区间被我们划分为:\([l,mid]\)和\([mid + 1, r]\)

while(l < r) {
	int mid = (l + r) / 2;
	if(A[mid] > key)  //如果要求大于等于,可以加上等于
		r = mid;  //因为要找的是大于key的第一个元素,A[mid]已经大于key了,所以mid + 1后面的排除
	else 
		l = mid + 1;  //如果A[mid]小于key,那么A[mid]以及比A[mid]小的数都需要排除
}

第三套模板也适合答案在一个区间内,而我们要求出满足题意的最后一个元素,也就是小于等于key的最后一个元素

区间被我们划分为\([l, mid - 1]\)和\([mid, r]\)

while(l < r) {
	int mid = (l + r + 1) / 2;  //这里要加上1,考虑如下一种情况,最后只剩下A[i],A[i + 1],如果不加1,那么mid = i,如果A[mid] < key,执行更新操作后,left = mid,right = mid + 1,就会是死循环
	if(A[mid] < key) 
		l = mid;  //如果A[mid]小于key,说明比A[mid]更小的数肯定不是小于key的最大的元素了,所以要排除mid之前的所有元素
	else   //反之,如果大了,那就说明比A[mid]更大的数肯定不可能为答案,所以排除mid及其之后的所有元素
		r = mid - 1;
}

最后两种情况的循环跳出条件是left<right,为什么不是小于等于呢?因为我们的区间变换思路是不断的舍去不可能是解的区间,最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解,所以需要使用小于等于

实数二分

实数二分就很好写了,不用考虑边界问题

while(r - l < 1e-8) {  //因为精度问题,所以这里不能用l < r了,而是需要迭代很多次直到l与r差别不大
        double mid = (l + r) / 2;
        if(check(mid) < key )  //随便写
            mid = r;
        else
            mid = l;
    }

立志成为一名攻城狮
最后更新于 2020-07-25