搜索

本章重点探讨搜索和排序，它们是最常见的计算机科学问题。本节探讨搜索，5.3节研究排序。搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回 True 或 False，分别表示元素是否存在。有时，可以修改搜索过程，使其返回目标元素的位置。不过，本节仅考虑元素是否存在。

Python 提供了运算符 in，通过它可以方便地检查元素是否在列表中。

>>> 15 in [3, 5, 2, 4, 1]
False
>>> 3 in [3, 5, 2, 4, 1]
True
>>>

尽管写起来很方便，但是必须经过一个深层的处理过程才能获得结果。事实上，搜索算法有很多种，我们感兴趣的是这些算法的原理及其性能差异。

顺序搜索

存储于列表等集合中的数据项彼此存在线性或顺序的关系，每个数据项的位置与其他数据项相关。在 Python 列表中，数据项的位置就是它的下标。因为下标是有序的，所以能够顺序访问，由此可以进行 顺序搜索。

图5-1展示了顺序搜索的原理。从列表中的第一个元素开始，沿着默认的顺序逐个查看，直到找到目标元素或者查完列表。如果查完列表后仍没有找到目标元素，则说明目标元素不在列表中。

Figure 1. 图5-1 在整数列表中进行顺序搜索

顺序搜索算法的 Python 实现如代码清单5-1 所示。这个函数接受列表与目标元素作为参数，并返回一个表示目标元素是否存在的布尔值。布尔型变量 found 的初始值为 False，如果找到目标元素，就将它的值改为 True。

代码清单5-1 无序列表的顺序搜索

def sequentialSearch(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


testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

分析顺序搜索算法

在分析搜索算法之前，需要定义计算的基本单元，这是解决此类问题的第一步。对于搜索来说，统计比较次数是有意义的。每一次比较只有两个结果：要么找到目标元素，要么没有找到。本节做了一个假设，即元素的排列是无序的。也就是说，目标元素位于每个位置的可能性都一样大。

要确定目标元素不在列表中，唯一的方法就是将它与列表中的每个元素都比较一次。如果列表中有 n 个元素，那么顺序搜索要经过 n 次比较后才能确定目标元素不在列表中。如果列表包含目标元素，分析起来更复杂。实际上有 3 种可能情况，最好情况是目标元素位于列表的第一个位置，即只需比较一次；最坏情况是目标元素位于最后一个位置，即需要比较 n 次。

普通情况又如何呢？我们会在列表的中间位置处找到目标元素，即需要比较 n/2 次。当 n 变大时，系数会变得无足轻重，所以顺序搜索算法的时间复杂度是 \$O(n)\$。表5-1 总结了 3 种可能情况的比较次数。

Figure 2. 表5-1 在无序列表中进行顺序搜索时的比较次数

前面假设列表中的元素是无序排列的，相互之间没有关联。如果元素有序排列，顺序搜索算法的效率会提高吗？

假设列表中的元素按升序排列。如果存在目标元素，那么它出现在 n 个位置中任意一个位置的可能性仍然一样大，因此比较次数与在无序列表中相同。不过，如果不存在目标元素，那么搜索效率就会提高。图5-2 展示了算法搜索目标元素 50 的过程。注意，顺序搜索算法一路比较列表中的元素，直到遇到 54。该元素蕴含额外的信息：54 不仅不是目标元素，而且其后的元素也都不是，这是因为列表是有序的。因此，算法不需要搜完整个列表，比较完 54 之后便可以立即停止。代码清单5-2 展示了有序列表的顺序搜索函数。

Figure 3. 图5-2 在有序整数列表中进行顺序搜索

代码清单5-2 有序列表的顺序搜索

def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos = pos + 1

    return found


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))

表5-2 总结了在有序列表中顺序搜索时的比较次数。在最好情况下，只需比较一次就能知道目标元素不在列表中。普通情况下，需要比较 n/2 次，不过算法的时间复杂度仍是 \$O(n)\$。总之，只有当列表中不存在目标元素时，有序排列元素才会提高顺序搜索的效率。

Figure 4. 表5-2 在有序列表中进行顺序搜索时的比较次数

二分搜索

如果在比较时更聪明些，还能进一步利用列表有序这个有利条件。在顺序搜索时，如果第一个元素不是目标元素，最多还要比较 n-1 次。但二分搜索不是从第一个元素开始搜索列表，而是从中间的元素着手。如果这个元素就是目标元素，那就立即停止搜索；如果不是，则可以利用列表有序的特性，排除一半的元素。如果目标元素比中间的元素大，就可以直接排除列表的左半部分和中间的元素。这是因为，如果列表包含目标元素，它必定位于右半部分。

接下来，针对右半部分重复二分过程。从中间的元素着手，将其和目标元素比较。同理，要么直接找到目标元素，要么将右半部分一分为二，再次缩小搜索范围。图5-3 展示了二分搜索算法如何快速地找到元素 54，完整的函数如代码清单5-3 所示。

Figure 5. 图5-3 在有序整数列表中进行二分搜索

代码清单5-3 有序列表的二分搜索

def binarySearch(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


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

请注意，这个算法是分治策略的好例子。分治是指将问题分解成小问题，以某种方式解决小问题，然后整合结果，以解决最初的问题。对列表进行二分搜索时，先查看中间的元素。如果目标元素小于中间的元素，就只需要对列表的左半部分进行二分搜索。同理，如果目标元素更大，则只需对右半部分进行二分搜索。两种情况下，都是针对一个更小的列表递归调用二分搜索函数，如代码清单5-4 所示。

代码清单5-4 二分搜索的递归版本

def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint + 1:], item)


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42, ]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

分析二分搜索算法

在进行二分搜索时，每一次比较都将待考虑的元素减半。那么，要检查完整个列表，二分搜索算法最多要比较多少次呢？假设列表共有 n 个元素，第一次比较后剩下 n/2 个元素，第 2 次比较后剩下 n/4 个元素，接下来是 n/4，然后是 n/16，依此类推。列表能拆分多少次呢？表5-3 给出了答案。

Figure 6. 表5-3 二分搜索算法的表格分析

拆分足够多次后，会得到只含一个元素的列表。这个元素要么就是目标元素，要么不是。无论是哪种情况，计算工作都已完成。要走到这一步，需要比较 i 次，其中 \$n/2^i=1\$。由此可得，\$i=logn\$。比较次数的最大值与列表的元素个数是对数关系。所以，二分搜索算法的时间复杂度是 \$O(logn)\$。

还有一点要注意。在代码清单5-4 中，递归调用 binarySearch(alist[:midpoint],item) 使用切片运算符得到列表的左半部分，并将其传给下一次调用（右半部分类似）。前面的分析假设切片操作所需的时间固定，但实际上在 Python 中，切片操作的时间复杂度是 \$O(k)\$。这意味着若采用切片操作，那么二分搜索算法的时间复杂度不是严格的对数阶。所幸，通过在传入列表时带上头和尾的下标，可以弥补这一点。作为练习，请参考代码清单5-3 计算下标。

尽管二分搜索通常优于顺序搜索，但当 n 较小时，排序引起的额外开销可能并不划算。实际上应该始终考虑，为了提高搜索效率，额外排序是否值得。如果排序一次后能够搜索多次，那么排序的开销不值一提。然而，对于大型列表而言，只排序一次也会有昂贵的计算成本，因此从头进行顺序搜索可能是更好的选择。

散列

我们已经利用元素在集合中的位置完善了搜索算法。举例来说，针对有序列表，可以采用二分搜索（时间复杂度为对数阶）找到目标元素。本节将尝试更进一步，通过散列构建一个时间复杂度为 \$O(1)\$ 的数据结构。

要做到这一点，需要了解更多关于元素位置的信息。如果每个元素都在它该在的位置上，那么搜索算法只需比较一次即可。不过，我们在后面会发现，事实往往并非如此。

散列表是元素集合，其中的元素以一种便于查找的方式存储。散列表中的每个位置通常被称为槽，其中可以存储一个元素。槽用一个从 0 开始的整数标记，例如 0 号槽、1 号槽、2 号槽，等等。初始情形下，散列表中没有元素，每个槽都是空的。可以用列表来实现散列表，并将每个元素都初始化为 Python 中的特殊值 None。图5-4 展示了大小 m 为 11 的散列表。也就是说，表中有 m 个槽，编号从 0 到 10。

Figure 7. 图5-4 有11个槽的散列表

散列函数将散列表中的元素与其所属位置对应起来。对散列表中的任一元素，散列函数返回一个介于 0 和 m-1 之间的整数。假设有一个由整数元素 54、26、93、17、77 和 31 构成的集合。首先来看第一个散列函数，它有时被称作 “取余函数”，即用一个元素除以表的大小，并将得到的余数作为散列值（h(item) =item%11）。表5-4 给出了所有示例元素的散列值。取余函数是一个很常见的散列函数，这是因为结果必须在槽编号范围内。

Figure 8. 表5-4 使用余数作为散列值

计算出散列值后，就可以将每个元素插入到相应的位置，如图5-5 所示。注意，在 11 个槽中，有 6 个被占用了。占用率被称作载荷因子，记作 λ，定义如下。

Figure 9. 图5-5 有6个元素的散列表

在本例中，\$λ=6/11\$

搜索目标元素时，仅需使用散列函数计算出该元素的槽编号，并查看对应的槽中是否有值。因为计算散列值并找到相应位置所需的时间是固定的，所以搜索操作的时间复杂度是 \$O(1)\$。如果一切正常，那么我们就已经找到了常数阶的搜索算法。

可能你已经看出来了，只有当每个元素的散列值不同时，这个技巧才有用。如果集合中的下一个元素是 44，它的散列值是 0（44%11==0），而 77 的散列值也是 0，这就有问题了。散列函数会将两个元素都放入同一个槽，这种情况被称作冲突，也叫 “碰撞”。显然，冲突给散列函数带来了问题，我们稍后详细讨论。

散列函数
给定一个元素集合，能将每个元素映射到不同的槽，这种散列函数称作完美散列函数。如果元素已知，并且集合不变，那么构建完美散列函数是可能的。不幸的是，给定任意一个元素集合，没有系统化方法来保证散列函数是完美的。所幸，不完美的散列函数也能有不错的性能。

构建完美散列函数的一个方法是增大散列表，使之能容纳每一个元素，这样就能保证每个元素都有属于自己的槽。当元素个数少时，这个方法是可行的，不过当元素很多时，就不可行了。如果元素是 9 位的社会保障号，这个方法需要大约 10 亿个槽。如果只想存储一个班上 25 名学生的数据，这样做就会浪费极大的内存空间。

我们的目标是创建这样一个散列函数：冲突数最少，计算方便，元素均匀分布于散列表中。有多种常见的方法来扩展取余函数，下面介绍其中的几种。

折叠法先将元素切成等长的部分（最后一部分的长度可能不同），然后将这些部分相加，得到散列值。假设元素是电话号码 436-555-4601，以 2 位为一组进行切分，得到 43、65、55、46 和 01。将这些数字相加后，得到 210。假设散列表有 11 个槽，接着需要用 210 除以 11，并保留余数 1。所以，电话号码 436-555-4601 被映射到散列表中的 1 号槽。有些折叠法更进一步，在加总前每隔一个数反转一次。就本例而言，反转后的结果是：43+56+55+64+01=219,219%11=10。

另一个构建散列函数的数学技巧是平方取中法：先将元素取平方，然后提取中间几位数。如果元素是 44，先计算 44²=1936，然后提取中间两位 93，继续进行取余的步骤，得到 5（93%11）。表5-5 分别展示了取余法和平方取中法的结果，请确保自己理解这些值的计算方法。

Figure 10. 表5-5 取余法和平方取中法的对比

我们也可以为基于字符的元素（比如字符串）创建散列函数。可以将单词 “cat” 看作序数值序列，如下所示。
>>> ord('c') 99 >>> ord('a') 97 >>> ord('t') 116
因此，可以将这些序数值相加，并采用取余法得到散列值，如图5-6 所示。代码清单5-5 给出了 hash 函数的定义，传入一个字符串和散列表的大小，该函数会返回散列值，其取值范围是 0 到 tablesize-1。

Figure 11. 图5-6 利用序数值计算字符串的散列值
代码清单5-5 为字符串构建简单的散列函数
def hash(astring, tablesize): sum = 0 for pos in range(len(astring)): sum = sum + ord(astring[pos]) return sum%tablesize
有趣的是，针对异序词，这个散列函数总是得到相同的散列值。要弥补这一点，可以用字符位置作为权重因子，如图5-7 所示。作为练习，请修改 hash 函数，为字符添加权重值。

Figure 12. 图5-7 在考虑权重的同时，利用序数值计算字符串的散列值

你也许能想到多种计算散列值的其他方法。重要的是，散列函数一定要高效，以免它成为存储和搜索过程的负担。如果散列函数过于复杂，计算槽编号的工作量可能比在进行顺序搜索或二分搜索时的更大，这可不是散列的初衷。
处理冲突

现在回过头来解决冲突问题。当两个元素被分到同一个槽中时，必须通过一种系统化方法在散列表中安置第二个元素。这个过程被称为处理冲突。前文说过，如果散列函数是完美的，冲突就永远不会发生。然而，这个前提往往不成立，因此处理冲突是散列计算的重点。

一种方法是在散列表中找到另一个空槽，用于放置引起冲突的元素。简单的做法是从起初的散列值开始，顺序遍历散列表，直到找到一个空槽。注意，为了遍历散列表，可能需要往回检查第一个槽。这个过程被称为开放定址法，它尝试在散列表中寻找下一个空槽或地址。由于是逐个访问槽，因此这个做法被称作 线性探测。

现在扩展表5-4 中的元素，得到新的整数集合（54, 26, 93, 17, 77, 31, 44, 55,20），图5-8 展示了新整数集合经过取余散列函数处理后的结果。请回顾图5-5 所示的初始内容。当我们尝试把 44 放入 0 号槽时，就会产生冲突。采用线性探测，依次检查每个槽，直到找到一个空槽，在本例中即为 1 号槽。

Figure 13. 图5-8 采用线性探测处理冲突

同理，55 应该被放入 0 号槽，但是为了避免冲突，必须被放入 2 号槽。集合中的最后一个元素是 20，它的散列值对应 9 号槽。因为 9 号槽中已有元素，所以开始线性探测，依次访问 10 号槽、0号槽、1号槽和 2 号槽，最后找到空的 3 号槽。

一旦利用开放定址法和线性探测构建出散列表，即可使用同样的方法来搜索元素。假设要查找元素 93，它的散列值是 5。查看 5 号槽，发现槽中的元素就是 93，因此返回 True。如果要查找的是 20，又会如何呢？20 的散列值是 9，而 9 号槽中的元素是 31。因为可能有冲突，所以不能直接返回 False，而是应该从 10 号槽开始进行顺序搜索，直到找到元素 20 或者遇到空槽。

线性探测有个缺点，那就是会使散列表中的元素出现聚集现象。也就是说，如果一个槽发生太多冲突，线性探测会填满其附近的槽，而这会影响到后续插入的元素。在尝试插入元素 20 时，要越过数个散列值为 0 的元素才能找到一个空槽。图5-9 展示了这种聚集现象。

Figure 14. 图5-9 散列值为0的元素聚集在一起

要避免元素聚集，一种方法是扩展线性探测，不再依次顺序查找空槽，而是跳过一些槽，这样做能使引起冲突的元素分布得更均匀。图5-10 展示了采用 “加3” 探测策略处理冲突后的元素分布情况。发生冲突时，为了找到空槽，该策略每次跳两个槽。

Figure 15. 图5-10 采用“加3”探测策略处理冲突

再散列 泛指在发生冲突后寻找另一个槽的过程。采用线性探测时，再散列函数是 newhashvalue = rehash(oldhashvalue)，并且 rehash(pos) = (pos +1)%sizeoftable。“加3” 探测策略的再散列函数可以定义为 rehash(pos) = (pos + 3)%sizeoftable。也就是说，可以将再散列函数定义为 rehash(pos) = (pos +skip)%sizeoftable。注意，“跨步”（skip）的大小要能保证表中所有的槽最终都被访问到，否则就会浪费槽资源。要保证这一点，常常建议散列表的大小为素数，这就是本例选用 11 的原因。

平方探测 是线性探测的一个变体，它不采用固定的跨步大小，而是通过再散列函数递增散列值。如果第一个散列值是h，后续的散列值就是 h+1、h+4、h+9、h+16，等等。换句话说，平方探测的跨步大小是一系列完全平方数。图5-11 展示了采用平方探测处理后的结果。

Figure 16. 图5-11 采用平方探测处理冲突

另一种处理冲突的方法是让每个槽有一个指向元素集合（或链表）的引用。链接法允许散列表中的同一个位置上存在多个元素。发生冲突时，元素仍然被插入其散列值对应的槽中。不过，随着同一个位置上的元素越来越多，搜索变得越来越困难。图5-12 展示了采用链接法解决冲突后的结果。

Figure 17. 图5-12 采用链接法处理冲突

搜索目标元素时，我们用散列函数算出它对应的槽编号。由于每个槽都有一个元素集合，因此需要再搜索一次，才能得知目标元素是否存在。链接法的优点是，平均算来，每个槽的元素不多，因此搜索可能更高效。本节最后会分析散列算法的性能。
实现映射抽象数据类型
字典是最有用的 Python 集合之一。第1章说过，字典是存储键-值对的数据类型。键用来查找关联的值，这个概念常常被称作映射。

映射抽象数据类型定义如下。它是将键和值关联起来的无序集合，其中的键是不重复的，键和值之间是一一对应的关系。映射支持以下操作。
- Map() 创建一个空的映射，它返回一个空的映射集合。
- put(key, val) 往映射中加入一个新的键-值对。如果键已经存在，就用新值替换旧值。
- get(key) 返回 key 对应的值。如果 key 不存在，则返回 None。
- del 通过 del map[key] 这样的语句从映射中删除键-值对。
- len() 返回映射中存储的键-值对的数目。
- in 通过 key in map 这样的语句，在键存在时返回 True，否则返回 False。
使用字典的一大优势是，给定一个键，能很快找到其关联的值。为了提供这种快速查找能力，需要能支持高效搜索的实现方案。虽然可以使用列表进行顺序搜索或二分搜索，但用前面描述的散列表更好，这是因为散列搜索算法的时间复杂度可以达到 \$O(1)\$。

代码清单5-6 使用两个列表创建 HashTable 类，以此实现映射抽象数据类型。其中，名为 slots 的列表用于存储键，名为 data 的列表用于存储值。两个列表中的键与值一一对应。在本节的例子中，散列表的初始大小是 11。尽管初始大小可以任意指定，但选用一个素数很重要，这样做可以尽可能地提高冲突处理算法的效率。
代码清单5-6 HashTable类的构造方法
class HashTable: def __init__(self): self.size = 11 self.slots = [None] * self.size self.data = [None] * self.size
在代码清单5-7 中，hashfunction 实现了简单的取余函数。处理冲突时，采用 “加1” 再散列函数的线性探测法。put 函数假设，除非键已经在 self.slots 中，否则总是可以分配一个空槽。该函数计算初始的散列值，如果对应的槽中已有元素，就循环运行 rehash 函数，直到遇见一个空槽。如果槽中已有这个键，就用新值替换旧值。
代码清单5-7 put函数
def put(self,key,data): hashvalue = self.hashfunction(key,len(self.slots)) if self.slots[hashvalue] == None: self.slots[hashvalue] = key self.data[hashvalue] = data else: if self.slots[hashvalue] == key: self.data[hashvalue] = data #replace else: nextslot = self.rehash(hashvalue,len(self.slots)) while self.slots[nextslot] != None and \ self.slots[nextslot] != key: nextslot = self.rehash(nextslot,len(self.slots)) if self.slots[nextslot] == None: self.slots[nextslot]=key self.data[nextslot]=data else: self.data[nextslot] = data #replace def hashfunction(self,key,size): return key%size def rehash(self,oldhash,size): return (oldhash+1)%size
同理，get 函数也先计算初始散列值，如代码清单5-8 所示。如果值不在初始散列值对应的槽中，就使用 rehash 确定下一个位置。注意，第 15 行确保搜索最终一定能结束，因为不会回到初始槽。如果遇到初始槽，就说明已经检查完所有可能的槽，并且元素必定不存在。

HashTable 类的最后两个方法提供了额外的字典功能。我们重载 __getitem__ 和 __setitem__，以通过 [] 进行访问。这意味着创建 HashTable 类之后，就可以使用熟悉的索引运算符了。其余方法的实现留作练习。
代码清单5-8 get函数
def get(self,key): startslot = self.hashfunction(key,len(self.slots)) data = None stop = False found = False position = startslot while self.slots[position] != None and \ not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position=self.rehash(position,len(self.slots)) if position == startslot: stop = True return data def __getitem__(self,key): return self.get(key) def __setitem__(self,key,data): self.put(key,data)
下面来看看运行情况。首先创建一个散列表并插入一些元素。其中，键是整数，值是字符串。
>>> H = HashTable() >>> H[54] = "cat" >>> H[26] = "dog" >>> H[93] = "lion" >>> H[17] = "tiger" >>> H[77] = "bird" >>> H[31] = "cow" >>> H[44] = "goat" >>> H[55] = "pig" >>> H[20] = "chicken" >>> H.slots [77, 44, 55, 20, 26, 93, 17, None, None, 31, 54] >>> H.data ['bird', 'goat', 'pig', 'chicken', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat']
接下来，访问并修改散列表中的某些元素。注意，键 20 的值已被修改。
>>> H[20] 'chicken' >>> H[17] 'tiger' >>> H[20] = 'duck' >>> H[20] 'duck' >>> H.data ['bird', 'goat', 'pig', 'duck', 'dog', 'lion', 'tiger', None, None, 'cow', 'cat'] >>> print(H[99]) None
分析散列搜索算法