Python数据结构与算法(2)查找

学习目标：

• 什么是列表查找？
• 顺序查找
• 二分查找
• 什么时候用哪个查找？

什么叫列表查找？

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

列表查找：从列表中查找指定元素。

输入：列表、带查找元素

输出：元素下标（None或者-1因为下标从0开始）

顺序查找

定义：也叫线性查找，从列表第一个元素开始，顺序依次进行搜索，直到找到待查找的元素（查找成功的情况）或者查找到最后一个元素返回None或者-1（查找未成功）。

顺序查找的时间复杂度为O(n)

1
2
3
4
5
6

def linear_search(li, val):
    for index, v in enumerate(li):
        if v == val:
            return index
    else:
        return None

二分查找（折半查找）

定义：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区的中间值进行比较，可以使候选区减少一半。候选区的意思是待查找的值可能出现的位置。

具体的实现方法：先将列表排序，用两个变量left（下标为0）和right（下标为n-1，n为列表长度）来求mid（下标是$(n-1)//2$），如果发现值比中间值小（候选区在mid左边），那么将right的值变为mid-1，然后计算新的mid值，再次进行比较，如果发现值比中间值大（候选区在mid右边），那么将left的值变为mid+1，计算新的mid值，如此往复。直到mid值为待查找值则成果查找或right值小于left则失败查找，则停止往复操作。

二分查找的时间复杂度为O(logn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def binary_search(li,val):
    left = 0
    right = len(li)-1
    li.sort()
    while left <= right: # 候选区有值
        mid = (left+right) //2
        if li[mid] == val:  # mid值查找成果
            return mid
        elif li[mid] > val: # 待查找的值在mid左侧
            right = mid -1 # 放弃右选区
        else:
            left = mid + 1  # 放弃左选区
    else:
        return None

什么时候使用哪种查找？

内置列表查找函数index()使用的是线性查找，二分查找要求列表是有序列表，二分查找快，但是有前提，排序的时间复杂度一般大于O(n)，如果数据已经排序好，使用二分查找效率高，但是数据无序的情况下还是使用顺序查找。

总结