python二分查找算法的例子

发布时间:2019-09-08编辑:脚本学堂
本文介绍下,在python编程中,实现二分查找算法的一个例子,有需要的朋友不妨参考学习下。

本节内容:
python二分查找算法

二分查找可以解决(预排序数组的查找)问题:
只要数组中包含T(即要查找的值),那么通过不断缩小包含T的范围,最终就可以找到它。
一开始,范围覆盖整个数组。将数组的中间项与T进行比较,可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,
最终就会在数组中找到T,或者确定原以为T所在的范围实际为空。对于包含N个元素的表,整个查找过程大约要经过log(2)N次比较。

例子:
 

复制代码 代码示例:
>>> def find(self, num): 
l = len(self) 
first = 0 
end = l - 1 
mid = 0 
if l == 0: 
self.insert(0,num) 
return False 
while first < end: 
mid = (first + end)/2 
if num > self[mid]: 
first = mid + 1 
elif num < self[mid]: 
end = mid - 1 
else: 
break 
if first == end: 
if self[first] > num: 
self.insert(first, num) 
return False 
elif self[first] < num: 
self.insert(first + 1, num) 
return False 
else: 
return True 
elif first > end: 
self.insert(first, num) 
return False 
else: 
return True 
 
>>> list_d = ['a','b','c','d','e','f','d','t'] 
>>> value_d = 't' 
>>> aa=find(list_d,value_d) 
>>> aa 
True 
>>> value_d='ha' 
>>> aa=find(list_d,value_d) 
>>> aa 
False