什么是列表查找

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

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

​ 输入：列表，待查找元素

​ 输出：元素下标（未找到元素时一般返回None或-1）

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

顺序查找(Linear Search)

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

def Linear_search(li, val):
    for ind, v in enumerate(li):
        if v == val:
            return ind
        else:
            return None
1
2
3
4
5
6

二分法查找 (Binary Search)

二分查找：又叫折半查找，从有序列表初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以是候选区减少一半。(二分法的前提是要有排序)

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