Python实现二分查找
上一篇 /
下一篇 2014-03-02 17:29:22
/ 个人分类：Python
#encoding=utf-8
#二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
#因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
#首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较。。
def BinarySearch(list,data):
stai = 0 #查询段的最前值的索引
endi = len(list) #查询段的最后值的索引
mid = endi/2 #查询段的中间值的索引
while True:
if data == list[mid]:
return mid
elif data < list[mid]:
endi = mid
mid = (endi + stai)/2
else:
stai = mid
mid = stai + (endi - stai)/2
#测试
list = [10,11,12,13,14,15,18,19,32,56,78,90,92,98,100]
print BinarySearch(list,18)
收藏
举报
TAG:
