便宜VPS测评
在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索引，查找结束。
