04-线性搜索

2.1.2　线性搜索

基因需要执行的一项基本操作就是搜索指定的密码子，目标就是简单地查找该密码子是否存在于基因中。

线性搜索（linear search）算法将按照原始数据结构的顺序遍历搜索空间（search space）中的每个元素，直到找到搜索内容或到达数据结构的末尾。其实对搜索而言，线性搜索是最简单、最自然、最显而易见的方式。在最坏的情况下，线性搜索将需要遍历数据结构中的每个元素，因此它的复杂度为O(n)，其中n是数据结构中元素的数量，如图2-2所示。

线性搜索函数的定义非常简单。它只需要遍历数据结构中的每个元素，并检查每个元素是否与所查找的数据相等。代码清单2-6所示的代码就对 Gene 和 Codon 定义了这样一个函数，然后尝试对 my_gene 和名为 acg 和 gat 的 Codon 对象调用这个函数。

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

def linear_contains(gene: Gene, key_codon: Codon) -> bool:
    for codon in gene:
        if codon == key_codon:
            return True
    return False
acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)
print(linear_contains(my_gene, acg))  # True
print(linear_contains(my_gene, gat))  # False

注意 　上述函数仅供演示。Python内置的序列类型（ list 、 tuple 、 range ）都已实现了 __contains__() 方法，这样就能简单地用 in 操作符在其中搜索某个指定的数据项。实际上， in 运算符可以与任何已实现 __contains__() 方法的类型一起使用。例如，执行 print(acg in my_gene) 语句即可在 my_gene 中搜索 acg 并打印出结果。