在python中二分查找法实现-图灵python

如果想要在有序数据中进行查找想要的数据，二分查找法就个好方法，它可以大大缩短了搜索时间，是一种常见的查找方法。二分查找很好写，却很难写对，下面，小编就简单向大家介绍一下二分查找，并演示器使用代码。

1、二分查找：在一个有序并且无重复的列表中，对该列表的元素进行查找。

2、特点

（1）必须针对于有序列表

（2）该列表必须无重复

（3）按下标索引查找

3、使用方法

非递归实现：

defbinary_search(alist,item):
"""二分查找非递归方式"""
n=len(alist)
start=0
end=n-1
whilestart<=end:
mid=(start+end)//2
ifalist[mid]==item:
returnTrue
elifitem<alist[mid]:
end=mid-1
else:
start=mid+1
returnFalse


if__name__=='__main__':
li=[17,20,26,31,44,54,55,77,93]
#print(binary_search(li,55))
#print(binary_search(li,100))

递归实现：

defbinary_search_2(alist,item):
"""二分查找递归方式"""
n=len(alist)
if0==n:
returnFalse
mid=n//2
ifalist[mid]==item:
returnTrue
elifitem<alist[mid]:
returnbinary_search_2(alist[:mid],item)
else:
returnbinary_search_2(alist[mid+1:],item)


if__name__=='__main__':
li=[17,20,26,31,44,54,55,77,93]
#print(binary_search(li,55))
#print(binary_search(li,100))

虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费O(nlgn)的时间。而且二分查找只适用顺序存储结构，链表上无法实现二分查找。小伙伴们要注意哦~