[编程笔记]-Binary_Search二分查找

前言

二分也算是比较普遍且常用的一个算法了，并且在前期还是个小难点，其相对复杂的类型以及边界问题通常让蒟蒻们很是头疼。

这一篇博客主要讲解二分查找的原理、模板等（不是二分答案），并不着重深入讲解其各种变式。

就这样吧(～￣▽￣)～

原理

二分查找就是把一段元素分成两半，用中间值进行对比，判断查找元素在其左侧或右侧，并在那一半进行查找，以到达O(logn)的复杂度。

因此，理论上来说，所有单调性问题都可以用二分解决。当然，并非只有单调性问题才可以用二分解决。

实现

概述

二分的实现其实并不难，搞清楚原理后，基本上就没什么问题了。

这里还是大概贴下思路：

1. 确定搜索范围。
2. 获取中间值。！注意，不同二分方式在这一步的具体实现会有所不同，详见下方！
3. 判断答案在左侧还是右侧。
4. 在答案所在一侧重新二分，循环直到范围缩为1。
5. 判断获得元素是否为所求，若否，则搜索范围中无需要元素。

整数二分

整数二分有两种形式，我个人将其命名为左倾二分以及右倾二分（非！官！方！命！名！）

左倾二分

定义

所谓_左倾_，就是说搜索到的答案倾向于向左侧靠近。举例地说，当一段元素中有连续的一段相同元素时，搜索此元素，得到的将会是这一段中最左侧的坐标。

实现方式

• 在计算中间坐标时，向下取整。原因会在第二点给出。
• 若中间值大于或等于答案，则将右边界重设为中间坐标。因此，中间坐标需向下取整，否则会陷入死循环。
• 否则，将左边界重设为中间坐标**+1**，原因是中间坐标已经确定不是答案，因此不在搜索范围内。

左倾原因

若当前搜索范围内值都一致，则都满足大于或等于答案，那么会一直重设右边界。同时，中间坐标向下取整，故而范围会一直向左缩小，直到缩小至一个元素，那么就是最左侧的元素了。

右倾二分

定义

_右倾_定义可借鉴_左倾_，就是说搜索到的答案倾向于向右侧靠近，这里就不做具体阐释。

实现方式

• 在计算中间坐标时，向上取整。原因会在第三点给出。
• 若中间值大于答案，则将右边界重设为中间坐标**-1**，原因是中间坐标已经确定不是答案，因此不在搜索范围内。
• 否则，将左边界重设为中间坐标。因此，中间坐标需向上取整，否则会陷入死循环。

右倾原因

若当前搜索范围内值都一致，则都满足小于或等于答案，那么会一直重设左边界。同时，中间坐标向上取整，故而范围会一直向右缩小，直到缩小至一个元素，那么就是最右侧的元素了。

代码

代码中check函数不固定，视需求而定

左倾二分

int l=0,r=n-1;
while(l<r){
    int m=l+r>>1;
    if(check(m))r=m;
    else l=m+1;
}

右倾二分

int l=0,r=n-1;
while(l<r){
    int m=l+r+1>>1;
    if(check(m))r=m-1;
    else l=m;
}

浮点数二分

前言

浮点数二分相对于整数二分来说简单了很多，但需要注意的是，通常情况下是不能真正搜索到答案的，因此，当当前值与答案之间的差距足够小时，我们就视之为答案即可。

思路

和整数二分差不多，取中间值时不存在取整问题，边界开闭随个人喜好。

循环条件要写成边界之差大于一个较小值！（通常为1e-6以下，具体要求随题目而定）

tips: 若题目有要求，则差值至少比保留小数位数多两位。

代码

double l=0,r=x;
while(r-l>1e-6){
	double m=(l+r)/2;
	if(check(m))r=m;
	else l=m;
}

拓展

update: 2024/7/31
STL库中有两个快速实现二分查找的函数。

upper_bound()

查询第一个大于要求值的数，返回其迭代器。

故而，如果要获得其坐标，记得减去第一个元素的迭代器。

模板以vector为例。

int bfind(int num){
	return upper_bound(vec.begin(),vec.end(),num)-vec.begin();
}

lower_bound()

和上一个差不多，查询第一个大于等于要求值的数，返回其迭代器。

int bfind(int num){
	return lower_bound(vec.begin(),vec.end(),num)-vec.begin();
}

完结撒花o(￣︶￣)o