算法第二讲搜索(search) [1]

搜索返回True和False来表示元素是否在集合中。在Python中使用in这种简单的方式就能判断元素是否在list中。但是，本文关注的是底层的各种搜索方法。

目录

顺序搜索

搜索方式：在线性数据结构中，如list中，依照元素的顺序依次查找。

def sequential_search(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1
    return found

复杂度：O(n)。如果item在集合中，最好情况是对比1次，最坏情况是对比n次。如果item不在集合中，需要对比n次。

二分搜索

搜索方式：对于排序过的队列，通过比较队列中间元素和item的大小相等关系，来达到一次排除一半待比较元素的目的[2]。

def binary_search(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first < last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found

复杂度：O(logN)。每对比一次，需要对比的元素就减半n/2。假设，对比i次之后，所剩元素为1。n = 2的i次方，求解得，i=logN。

哈希搜索

见 哈希搜索 部分。

对比

如果想使用二分搜索，要时刻考虑到排序的开销是否值得。好比，如果集合不是很大，可能就不太需要二分搜索；又好比，这个集合虽然不是特别大，但是需要经常搜索，那一次排序可能就值得。

参考资料：

• Problem Solving with Algorithms and Data Structures - Chapter 5

注[1]: 其实我更喜欢叫查找。

注[2]: 将需要对比的元素减少一半，这是将一个大问题转换成同样类型的小问题。也可以使用递归的方式来是实现。

def binary_search_recursion(alist, item):
    # base case
    if len(alist) == 0:
        return False
    midpoint = len(alist) // 2
    if alist[midpoint] == item:
        return True
    elif alist[midpoint] > item:
        return binary_search_recursion(alist[:midpoint-1], item)
    else:
        return binary_search_recursion(alist[midpoint+1:], item)