查找

• 意思：在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程
• 列表查找（线性表查找）：从列表中查找指定元素
  • 输入：列表、待查找元素
  • 输出：元素下标（未找到时一般返回None或-1）
• 内置列表查找函数：index()

顺序查找（Linear Search）

•  意思：也叫线性查找，从列表的第一个元素开始，顺序进行搜索，直到找到元素或搜索到列表的最后一个元素为止
• 时间复杂度O(n)

代码：

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

enumerate()函数

enumerate()函数用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标，一般用在for循环当中。

enumerate(sequence, [start=0])

•  sequence -- 一个序列、迭代器或其他支持迭代对象
• start -- 起始下标的值

二分查找（Binary Search）

•  意思：又叫折半查找，从有序列表的初始候选区li[0:n]开始，比较待查找的值与候选区中间值，可以使候选区减少一半
• 时间复杂度O(logn)

代码：

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:
            right = mid -1
        elif li[mid] < val:
            left = mid + 1
    else:
        return None