每个程序员都应该知晓的核心搜索算法 _搜索算法

“搜索”是一个宏大的主题，本书通篇都可被称为“用Python解决经典的搜索问题” 。本章将介绍每个程序员都应该知晓的核心搜索算法。别看标题很响亮，但本章内容其实称不上全面。
2.1　DNA搜索在计算机软件中，基因通常会表示为字符A、C、G和T的序列。每个字母代表一种核苷酸（nucleotide），3个核苷酸的组合称作密码子（codon）。如图2-1所示，密码子的编码决定了氨基酸的种类，多个氨基酸一起形成了蛋白质（protein）。生物信息学软件的一个经典任务就是在基因中找到某个特定的密码子。

文章插图

图2-1　核苷酸由A、C、G和T之一表示。密码子由3个核苷酸组成，基因由多个密码子组成
2.1.1　DNA的存储方案核苷酸可以表示为包含4种状态的简单类型IntEnum，如代码清单2-1所示。
代码清单2-1　dna_search.py
from enum import IntEnumfrom typing import Tuple, ListNucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))Nucleotide的类型是IntEnum，而不仅仅是Enum，因为IntEnum“免费”提供了比较运算符（<、>=等）。为了使要实现的搜索算法能完成这些操作，需要数据类型支持这些运算符。从typing包中导入Tuple和List，是为了获得类型提示提供的支持。
如代码清单2-2所示，Codon可以定义为包含3个Nucleotide的元组，Gene可以定义为Codon的列表。
代码清单2-2　dna_search.py（续）
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]# type alias for codonsGene = List[Codon]# type alias for genes

注意　尽管稍后需要对Codon进行相互比较，但是此处并不需要为Codon定义显式地实现了“<”操作符的自定义类，这是因为只要组成元组的元素类型是可比较的，Python就内置支持元组的比较操作。

互联网上的基因数据通常都是以文件格式提供的，其中包含了代表基因序列中所有核苷酸的超长字符串。下面将为某个虚构的基因定义这样一个字符串，并将其命名为gene_str，具体代码如代码清单2-3所示。
代码清单2-3　dna_search.py（续）
gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"这里还需要一个实用函数把str转换为Gene 。具体代码如代码清单2-4所示。
代码清单2-4　dna_search.py（续）

def string_to_gene(s: str) -> Gene:gene: Gene = []for i in range(0, len(s), 3):if (i + 2) >= len(s):# don't run off end!return gene#initialize codon out of three nucleotidescodon: Codon = (Nucleotide[s[i]], Nucleotide[s[i + 1]], Nucleotide[s[i + 2]])gene.Append(codon)# add codon to genereturn gene

string_to_gene()遍历给定的str，把每3个字符转换为Codon，并将其追加到新建的Gene的末尾。如果该函数发现从正在读取的s的当前位置开始不够放下两个Nucleotide的位置（参见循环中的if语句），就说明已经到达不完整基因的末尾了，于是最后一个或两个核苷酸就会被跳过。
string_to_gene()可用于把str类型的gene_str转换为Gene 。具体代码如代码清单2-5所示。
代码清单2-5　dna_search.py（续）
my_gene: Gene = string_to_gene(gene_str)2.1.2　线性搜索基因需要执行的一项基本操作就是搜索指定的密码子，目标就是简单地查找该密码子是否存在于基因中。
线性搜索（linear search）算法将按照原始数据结构的顺序遍历搜索空间（search space）中的每个元素，直到找到搜索内容或到达数据结构的末尾。其实对搜索而言，线性搜索是最简单、最自然、最显而易见的方式。在最坏的情况下，线性搜索将需要遍历数据结构中的每个元素，因此它的复杂度为