不光是查找值！“二分搜索”

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

一些模板

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

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

整数二分：

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

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;
    }