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

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

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

输入：列表中的待查找的元素输出：找到的元素的下标，如果未找到，一般返回None或者-1python中查找的内置方法：index()

顺序查找代码实现如下：

def linear_search(data,elem): for index,val in enumerate(data): if elem == val: return index return -1if __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 -1if __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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。