05-二分搜索

2.1.3　二分搜索

有一种搜索方法比查看每个元素速度快，但需要提前了解数据结构的顺序。如果我们知道某数据结构已经排过序，并且可以通过数据项的索引直接访问其中的每一个数据项，就可以执行二分搜索（binary search）。根据这一标准，已排序的Python List 是二分搜索的理想对象。

二分搜索的原理如下：查看一定范围内有序元素的中间位置的元素，将其与所查找的元素进行比较，根据比较结果将搜索范围缩小一半，然后重复上述过程。下面看一个具体的例子。

假定有一个按字母顺序排列的单词 List ，类似于 ["cat", "dog", "kangaroo", "llama", "rabbit", "rat", "zebra"] ，要查找的单词是“rat”。

（1）可以确定在这7个单词的列表中，中间位置的元素为“llama”。

（2）可以确定按字母顺序“rat”将排在“llama”之后，因此它一定位于“llama”之后的一半（近似）列表中。（如果在本步中已经找到“rat”，就应该返回它的位置；如果发现所查找的单词排在当前的中间单词之前，就可以确信它位于“llama”之前的一半列表中。）

（3）可以对“rat”有可能存在其中的半个列表再次执行第1步和第2步。这半个列表事实上就成了新的目标列表。这些步骤会持续执行下去，直至找到“rat”或者当前搜索范围中不再包含待查找的元素（意味着该单词列表中不存在“rat”）。

图2-3展示了二分搜索的过程。请注意，与线性搜索不同，它不需要搜索每个元素。

二分搜索将搜索空间不停地减半，因此它的最坏情况运行时间为O(lg n)。但是这里还有个排序问题。与线性搜索不同，二分搜索需要对有序的数据结构才能进行搜索，而排序是需要时间的。实际上，最好的排序算法也需要O(n lg n)的时间才能完成。如果我们只打算运行一次搜索，并且原数据结构未经排序，那么可能进行线性搜索就比较合理。但如果要进行多次搜索，那么用于排序所付出的时间成本就是值得的，获得的收益来自每次搜索大幅减少的时间成本。

为基因和密码子编写二分搜索函数，与为其他类型的数据编写搜索函数没什么区别，因为同为 Codon 类型的数据可以相互比较，而 Gene 类型只不过是一个 List 。具体代码如代码清单2-7所示。

代码清单2-7　dna_search.py（续）

def binary_contains(gene: Gene, key_codon: Codon) -> bool:
    low: int = 0
    high: int = len(gene) - 1
    while low <= high:  # while there is still a search space
        mid: int = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False

下面就逐行过一遍这个函数。

low: int = 0
high: int = len(gene) - 1

首先看一下包含整个列表（ gene ）的范围。

while low <= high:

只要还有可供搜索的列表范围，搜索就会持续下去。当 low 大于 high 时，意味着列表中不再包含需要查看的槽位（slot）了。

mid: int = (low + high) // 2

我们用整除法和在小学就学过的简单均值公式计算中间位置 mid 。

if gene[mid] < key_codon:
    low = mid + 1

如果要查找的元素大于当前搜索范围的中间位置元素，我们就修改下一次循环迭代时要搜索的范围，方法是将 low 移到当前中间位置元素后面的位置。下面是把下一次迭代的搜索范围减半的代码。

elif gene[mid] > key_codon:
    high = mid - 1

类似地，如果要查找的元素小于中间位置元素之前，就将当前搜索范围反向减半。

else:
    return True

如果当前查找的元素既不小于也不大于中间位置元素，就表示它就是要找的元素！当然，如果循环迭代完毕，就会返回 False ，以表明没有找到，这里就不重现代码了。

下面可以尝试用同一份基因数据和密码子运行函数了，但必须记得先进行排序。具体代码如代码清单2-8所示。

代码清单2-8　dna_search.py（续）

my_sorted_gene: Gene = sorted(my_gene)
print(binary_contains(my_sorted_gene, acg))  # True
print(binary_contains(my_sorted_gene, gat))  # False

提示 　可以用Python标准库中的 bisect 模块构建高性能的二分搜索方案。