学号：20113212846
姓名：李鑫磊
转载：https://blog.csdn.net/weixin_37780776/article/deta...
【嵌牛导读】经典递归算法二分查找的Python手动实现与复杂度分析
【嵌牛鼻子】数据结构 Python
文章目录
一、二分查找算法简介
二、二分查找算法实现
三、二分查找算法效率分析
当给定一个无序的序列时，如果需要在其中查找某目标值，则需要按顺序循环判断序列中的每一个值是否为目标值，这就是所谓的顺序查找法，很显然该算法的最坏时间复杂度为O(n)O(n)。
当给定一个有序序列且其中的元素均可以通过索引来访问（如下图所示），此时有一种更加高效的查找算法——二分查找。
一、二分查找算法简介
二分查找是针对有序且可索引序列的一种高效查找算法，该算法的核心是重复地将待搜索的区间折半，在查找的开始待搜索区间为整个序列，如果待查找的键小于当前区间中点索引对应的序列值，则将搜索的区间缩小为左半区间，否则将待搜索区间缩小为右半区间。重复该过程直到找到待搜索的键或区间变成空。
为更好的解释上面的描述，下图是对上图所示的有序序列data使用二分查找算法搜索目标值22的过程，其中使用了三个变量来完成查找过程：
low：待搜索区间最左侧元素的索引；
high：待搜索区间最右侧元素的索引；
mid：待搜索期间中点的索引(low+high) // 2。
具体地，二分查找的过程分为以下三个情况：
如果目标值等于data[mid]，则mid索引处保存了目标值，查找结束；
如果目标值小于data[mid]，则待搜索区间缩小至[low, mid - 1]，查找通过递归方式继续；
如果目标值大于data[mid]，则待搜索区间缩小至[mid + 1, high]，查找通过递归方式继续。
需要注意的是，为保证即使目标值不在待查找区间内程序递归调用也可以正常退出，要确保当low > high时程序返回。
二、二分查找算法实现
下面是二分查找算法的Python实现：def binary_search(data, target, low, high):
"""
二分查找算法实现
:param data: 待查找有序序列
:param target: 目标值
:param low: 待搜索区间下限
:param high: 待搜索区间上限
:return: 查找结果
"""
if low > high: # 待搜索区间为空
return False
else:
mid = (low + high) // 2
if target == data[mid]:
return True
elif target < data[mid]: # 目标值在左半区间
return binary_search(data, target, low, mid - 1)
else: # 目标值在右半区间
return binary_search(data, target, mid + 1, high)
三、二分查找算法效率分析
二分查找算法的最坏时间复杂度为O(logn)O(logn)，原因在于每一次调用binary_search都执行常数次基本操作，如果假设一开始待搜索区间的元素个数为nn，则最坏情况下：
第1次调用binary_search之后，待搜索区间的元素个数减少至n/2n/2；
第2次调用binary_search之后，待搜索区间的元素个数减少至n/4n/4；
⋅⋅⋅⋅⋅⋅
第jj次递归调用binary_search之后，待搜索区间的元素个数减少至n/2jn/2
j
；
⋅⋅⋅⋅⋅⋅
因此，递归调用的最大次数rr和元素个数nn之间的关系为：
n/2r<1
n/2
r
<1
故r>lognr>logn，即r=⌊logn⌋+1r=⌊logn⌋+1，证毕。
