欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法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)