二分查找算法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

二分查找算法

作者：

洛喑 , 2022-07-19 16:21:35 , 所有人可见 , 阅读 906

13

4

一、二分查找算法简介

1.介绍

二分查找也称折半查找（ $Binary Search$ ），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

中文名	外文名	别名	提出者	提出时间
二分查找	$Binary Search$	折半查找	$John \ Mauchly$	$1946$ 年

二分查找的优点是速度较快，时间复杂度为 $O(\log n)$ ，但是缺点是它需要查找数的这张表，必须有序。

4.算法思想

假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

这样我们就可以用 $O(\log n)$ 的时间复杂度，找出需要查找的数

3.查找过程

首先，表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较：

如果两者相等，则查找成功;
否则利用中间位置记录将表分成前、后两个子表，继续查找。

如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表；
否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

二、二分查找的实现

现在就是二分查找的实现了，二分查找实现有两种办法，一种是手写，另一种是用 $STL$ 。

1. $STL$ 实现

在 $C++$ 的 $STL$ 库中也是有二分查找的，但是要调用的话，记得要加上#include <algorithm>头文件。

(1)`binary_search()`

这个函数是在从小到大排好序的基本类型数组上进行二分查找。

binary_search(数组名 + n1, 数组名 + n2,需要查找的数);
n1表示从数组的第几位开始查找
n2表示查找到第几位

如果数组从 $0$ 开始， $n1$ 可以不写。

(2)`lower_bound()`

lower_bound(数组名 + n1, 数组名 + n2, 需要查找的数);

注意：这个函数返回的是查找出的数的下标，需要用一个指针来存储

找到是查找区间里下标最小的，大于等于值的元素。如果找不到，会指向下标为 $n2$ 的元素。因为n2不在查找区间内，如果要判断是否找到可以用这个作为依据。

(3)`upper_bound()`

upper_bound(数组名 + n1, 数组名 + n2, 需要查找的数);
注意：这个函数和 $lower\underline{~}bound()$ 一样返回的是查找出的数的下标，需要用一个指针来存储

找到的是查找区间里下标最小的，大于值的元素（这里是大于，不要和前面弄混了）。如果找不到，p指向下标为n2的元素。

2.二分查找算法模板

二分查找算法模板

40 评论

iwoeix 2022-07-19 16:28

$\LaTeX$ 崩了

洛喑 2022-07-19 16:29

洛喑 2022-07-19 16:30

你的意思是不是说看上去有点。。。难看

iwoeix 2022-07-19 18:30 回复了洛喑的评论

$lower_bound()$

iwoeix 2022-07-19 18:30 回复了 iwoeix 的评论

这是什么

iwoeix 2022-07-19 18:32 回复了 iwoeix 的评论

$lower\underline{~}bound()$

洛喑 2022-07-20 10:23 回复了 iwoeix 的评论

洛喑 2022-07-20 10:25 回复了 iwoeix 的评论

敲音猴，怎么弄的。。。

iwoeix 2022-07-20 10:26 回复了洛喑的评论

$lower\underline{~}bound()$

iwoeix 2022-07-20 10:26 回复了 iwoeix 的评论

$lower\underline{~}bound()$

iwoeix 2022-07-20 10:27 回复了 iwoeix 的评论

还有你的 $O(logn)$

iwoeix 2022-07-20 10:27 回复了 iwoeix 的评论

空格都没了

iwoeix 2022-07-20 10:27 回复了 iwoeix 的评论

格式也不对

iwoeix 2022-07-20 10:28 回复了 iwoeix 的评论

$O(\log n)$

洛喑 2022-07-20 10:45 回复了 iwoeix 的评论

空格我会弄hh

iwoeix 2022-07-20 10:46 回复了洛喑的评论

格式！

洛喑 2022-07-20 10:46 回复了 iwoeix 的评论

都搞好了应该

iwoeix 2022-07-20 10:46 回复了 iwoeix 的评论

\log不是log

iwoeix 2022-07-20 10:47 回复了 iwoeix 的评论

并没有搞好

洛喑 2022-07-20 10:49 回复了 iwoeix 的评论

哦

洛喑 2022-07-20 10:49 回复了 iwoeix 的评论

原来还有一个 $O(log \ n)$

iwoeix 2022-07-20 10:50 回复了洛喑的评论

\log！

iwoeix 2022-07-20 10:50 回复了 iwoeix 的评论

必须要用\log

洛喑 2022-07-20 10:50 回复了 iwoeix 的评论

你说的是 $O(\log n)$

iwoeix 2022-07-20 10:50 回复了洛喑的评论

用\log而不是log

洛喑 2022-07-20 10:51 回复了 iwoeix 的评论

哦，一定要这样吗

iwoeix 2022-07-20 10:51 回复了 iwoeix 的评论

我强迫症

洛喑 2022-07-20 10:51 回复了 iwoeix 的评论

两个不都差不多吗

洛喑 2022-07-20 10:51 回复了 iwoeix 的评论

额

洛喑 2022-07-20 10:52 回复了 iwoeix 的评论

这样不好看吗， $O(log \ n)$

iwoeix 2022-07-20 10:52 回复了洛喑的评论

必须！

iwoeix 2022-07-20 10:52 回复了 iwoeix 的评论

要不我点踩

洛喑 2022-07-20 10:52 回复了 iwoeix 的评论

额

洛喑 2022-07-20 10:52 回复了 iwoeix 的评论

~~珂是，我觉得 $O(log \ n)$ 更好看~~

iwoeix 2022-07-20 10:52 回复了洛喑的评论

搞不搞

洛喑 2022-07-20 10:54 回复了 iwoeix 的评论

额

洛喑 2022-07-20 10:55 回复了 iwoeix 的评论

行了喵

云衣醉梦 2023-08-22 21:16 回复了洛喑的评论

看到一样的强迫症人了捏
这是你古的审题解规则，比较规范
还有算法名真的不要用 LaTeX 啊…看不下去

云衣醉梦 2023-08-22 21:16 回复了云衣醉梦的评论

字母与汉字之间要加空格！！！早看不下去了怒了

App 内打开