分享
算法很美之二分查找(Binary search)
输入“/”快速插入内容
算法很美之
二分查找
(
Binary search
)
用户102
用户102
2023年10月29日修改
⏳
Written 05-08-2021
基本概念
当我们要从一个序列中查找一个元素的时候,
二分查找
是一种非常快速的查找算法,二分查找又叫
折半查找
。它对要查找的序列有两个要求,一是该序列必须是有序的(即该序列中的所有元素都是按照大小关系排好序的,升序和降序都可以,本文假设是升序排列的),二是该序列必须是顺序存储的。下图展示的就是能进行二分查找的序列。
💡
如果一个序列是无序的或者是
链表
,那么该序列就不能进行
二分查找
。之所以被查找的序列要满足这样的条件,是由二分查找算法的原理决定的
算法原理
二分查找
算法的原理如下:
1.
如果待查序列为空,那么就返回-1,并退出算法;这表示查找不到目标元素
2.
如果待查序列不为空,则将它的中间元素与要查找的目标元素进行匹配,看它们是否相等
3.
如果相等,则返回该中间元素的索引,并退出算法;此时就查找成功了
4.
如果不相等,就再比较这两个元素的大小
5.
如果该中间元素大于目标元素,那么就将当前序列的前半部分作为新的待查序列;这是因为后半部分的所有元素都大于目标元素,它们全都被排除了
6.
如果该中间元素小于目标元素,那么就将当前序列的后半部分作为新的待查序列;这是因为前半部分的所有元素都小于目标元素,它们全都被排除了
7.
在新的待查序列上重新开始第1步的工作
💡
二分查找
之所以快速,是因为它在匹配不成功的时候,每次都能排除剩余元素中一半的元素。因此可能包含目标元素的有效范围就收缩得很快,而不像顺序查找那样,每次仅能排除一个元素
算法模板
区间定义:
[l, r) 左闭右开
其中f(m)函数代表找到了满足条件的情况,如果存在就返回对应的位置
如果没有找到,就通过g(m)函数缩小查找的范围,继续查找
代码块
Python
def binary_search(l, r):
while l < r:
m = l + (r - l) // 2
if f(m): # 判断找了没有 (可选)
return m
if g(m): # 根据题目条件设置g(m)的策略
r = m # 新的查找范围 [l, m)
else:
l = m + 1 # 新的查找范围 [m+1, r)
return -1 # 还是没有找到 返回-1
💡
为什么
二分查找
的left=
mid
+1,不能是left=mid?
💡
这个和定义的区间有关,我们定义的查找的区间是[l, r),即左闭右开。即每次查找的范围已经包括了 left, 但是不包括 right。而
mid
的位置已经计算过了,所以下次不需要再判断mid。那么下次搜索的范围是[mid + 1, right)
当序列中出现重复元素的时候,我们可以根据题目要求选择对应的模板进行解决