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