​​使用Python实现二分查找算法！

在100个人中有1个人已被病毒感染，现在需要对这100个人进行快速排查，找出感染者，排查方法是抽血化验，每次验血需要1个小时的时间，当前只有1名化验员，在最坏的情况下，需要100个小时才能找出感染者。如何在最短的时间内找出感染者呢？
可以采用下面的方法：

将这100个人分为两组，50人为一组，每组混合所有人血液样本，分别对这两组的血液样本进行化验，可以排除不含病毒样本的组；对剩余的50人采用同样的化验方式，50人分为两组，每组25人，可以排除不含病毒样本的组；对剩余的25人采用同样的化验方式，……

最多经过7次分组就可以找到感染者，耗费的时间为14个小时。

第一次分组：化验2次，耗费2小时，排除50人，待排查50人；

第二次分组：化验2次，耗费2小时，排除25人，待排查25人；

第三次分组：化验2次，耗费2小时，排除13人，待排查12人；

第四次分组：化验2次，耗费2小时，排除6人，待排查6人；

第五次分组：化验2次，耗费2小时，排除3人，待排查3人；

第六次分组：化验2次，耗费2小时，排除1人，待排查2人；

第七次分组：化验2次，耗费2小时，确定感染者。

前面分组化验的方法就是二分查找法，它每次查找都会取一个中间值，将查找的范围缩小一半，条件是要将分组人的血液样本进行混合，这是二分查找的必要条件。

二分查找算法多应用在计算机程序查询场景。

从10000个无重复的英文单词库中查找英文单词，若采用顺序查找方法，在最坏的情况下，需要执行10000次查找。若使用二分查找，至多需要13次。

l 随着元素数量的增加，二分查找需要的额外时间并不多，而简单查询需要的额外时间却很多。因此二分查找的速度比顺序查找快的多。

实现二分查找的Python代码。

'''

功能：二分查找函数

参数：

num：待查找的元素

array: 已排序的列表对象

start: 查找的起始索引

end: 查找的终止索引

'''

def binay_search(num,array,start=None,end=None):

if start == None:

start = 0

if end == None:

end = len(array) - 1

mid = (end - start)//2 + start

if start > end:

return None

elif array[mid] > num :

return binay_search(num,array,start,mid-1)

elif array[mid] < num:

return binay_search(num,array,mid+1,end)

elif array[mid] == num:

return mid

# 程序入口

if __name__ == '__main__':

array= [num for num in range(100)]

print(binay_search(60,array))

函数binay_search实现了二分查找算法，参数num是待查找的元素，参数array是已排序的列表对象，参数start和end设定查找范围，默认为None，即查找范围为整个array列表。

二分查找算法的核心是利用二分思想，每次都与array的中间数据比对大小，缩小查找区间的范围。函数通过start和end确定array中间数据的索引mid。若mid指向的数据大于num，说明num在中间数据的左侧，递归调用binay_search函数，参数起始索引为start，终止索引为mid-1；若mid指向的数据小于num，说明num在中间数据的右侧，递归调用binay_search函数，参数起始索引为mid+1，终止索引为end；若若mid指向的数据等于num，返回mid索引，查找结束。

以上就是今天要分享的技巧，你学会了吗？若有什么问题，欢迎在下方留言。

学习资料见知识星球。

以上就是今天要分享的技巧，你学会了吗？若有什么问题，欢迎在下方留言。

快来试试吧，小琥 my21ke007。获取 1000个免费 Excel模板福利​​​​！

更多技巧， www.excelbook.cn

欢迎 加入 零售创新 知识星球，知识星球主要以数据分析、报告分享、数据工具讨论为主；