Py008-01-03查找算法

查找

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

列表查找(线性表查找)：从列表中查找指定元素

  • 输入：列表/待查找元素
  • 输出：元素下标（未找到元素时一般返回None或-1）

内置列表查找函数：index()

也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表最后一个元素为止

时间复杂度：O(n)

1
2
3
4
5
6
7
def linear_search(data_set,value):
    for i,v in enumerate(data_set):
        if v == value:
            return i
    return None

index = linear_search([1,2,3,5,4],4) # 4

二分查找

折半查找，从有序列表的初始候选区arr[0:n]开始，通过对待查找的值与候选区中间的值的比较，可以使候选区减少一半

猜物品价格 0-1000 假设物品840元

1
2
3
4
5
6
7
8
9
第一次 500  低了  + (1000-500)/2 = +250
第二次 750  低了  + (1000-750)/2 = +125
第三次 875  高了  - (875-750)/2 = -62.5
第四次 813  低了  + (875-813)/2 = +31
第五次 844  高了 - (844-813)/2 = -11.5
第六次 833  低了 + (844-833)/2 = +5.5
第七次 838  低了 + (844-838)/2 = +3
第七次 841  高了 - (841-838)/2 = -1.5
第八次 840  对了

二分查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search(li,val):
    left = 0
    right = len(li) - 1
    while left <= right: # 候选区有值
        # 中间值
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val: # 待查找的值在mid左侧
            right = mid - 1
        else: # li[mid] < val # 待查找的值在mid右侧
            left = mid + 1
    else:
        return None

a = binary_search([1,2,3,4,5,6,7,8,9],3) # 2

时间复杂度： O(log n)

二分查找比线性查找速度快

1
内置函数index() 就是线性查找，因为二分查找的要求就是有序列表