查找

查找可以说是我们业务代码里用得最多的操作，比如我们经常需要在一个列表里找到我们需要的一个元素，然后返回它的位置。 其实之前我们介绍的哈希表就是非常高效率的查找数据结构，很明显地它是用空间换时间。这一节介绍两个基本的基于线性结构的查找。

线性查找

线性查找就是从头找到尾，直到符合条件了就返回。比如在一个 list 中找到一个等于 5 的元素并返回下标：

number_list = [0, 1, 2, 3, 4, 5, 6, 7]


def linear_search(value, iterable):
    for index, val in enumerate(iterable):
        if val == value:
            return index
    return -1


assert linear_search(5, number_list) == 5

是不是 so easy。当然我们需要来一点花样，比如传一个谓词进去，你要知道，在 python 里一切皆对象，所以我们可以把函数当成一个参数传给另一个函数。

def linear_search_v2(predicate, iterable):
    for index, val in enumerate(iterable):
        if predicate(val):
            return index
    return -1


assert linear_search_v2(lambda x: x == 5, number_list) == 5

效果是一样的，但是传入一个谓词函数进去更灵活一些，比如我们可以找到第一个大于或者小于 5 的，从而控制函数的行为。 还能玩出什么花样呢？前面我们刚学习了递归，能不能发挥自虐精神没事找事用递归来实现呢？

def linear_search_recusive(array, value):
    if len(array) == 0:
        return -1
    index = len(array)-1
    if array[index] == value:
        return index
    return linear_search_recusive(array[0:index], value)