数据结构与算法python版(3)-列表顺序查找和二分查找(折半查找)
程序员文章站
2022-03-14 20:35:14
...
-
查找:在一些数据元素中,通过一定的方法找出与给定关键字相同的数据元素的过程
-
列表查找:从列表中查找指定的元素
- 输入:列表中的待查找的元素
- 输出:找到的元素的下标,如果未找到,一般返回None或者-1
- python中查找的内置方法:index()
-
顺序查找代码实现如下:
def linear_search(data,elem):
for index,val in enumerate(data):
if elem == val:
return index
return -1
if __name__=="__main__":
a=[1,2,3,4,5,6,7,8,9,0]
index=linear_search(a,9)
print("线性查找到的元素位置:",index)
执行结果如下:
线性查找到的元素位置: 8
-
顺序查找的时间复杂度为O(n)
-
二分查找:又叫折半查找,二分查找的前提是列表有序,通过对待查找的值不断的和中间值比较,使得查找的范围不断减半
-
代码实现如下:
def binary_search(data,elem):
left=0
right=len(data)-1
mid=(left+right)//2
while left<=right:
if elem==data[mid]:
return mid
elif elem>data[mid]:
left=mid
mid=(left+right)//2
else:
right=mid
mid=(left+right)//2
return -1
if __name__=="__main__":
a=[1,2,3,4,5,6,7,8,9,0]
index=binary_search(a,9)
print("线性查找到的元素位置:",index)
执行结果如下:
线性查找到的元素位置: 8
-
二分查找的复杂度为O(logn)
-
通过以上分析可以发现,当列表元素有序时,查找使用二分查找明显是最快的,如果列表无需,则可以考虑使用顺序查找,因为如果先将列表排序,则排序的时间复杂度一般都是大于 O(n)的
-
python的内置方法index()使用的就是线性查找,虽然二分查找很快,但是二分查找要求列表必须有序,而排序的复杂度比O(n)要打,而index()方法根本不知道列表是否有序,因此它使用的顺序查找,时间复杂度为O(n)
下一篇: 查找-二分查找(折半查找)