数据结构与算法python版（3）-列表顺序查找和二分查找（折半查找）

• 查找：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程
• 列表查找：从列表中查找指定的元素

• 输入：列表中的待查找的元素
• 输出：找到的元素的下标，如果未找到，一般返回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)