この記事は、オライリー社の書籍「Python計算機科学新教本」を学習した時の備忘録です。
二分探索
データ構造がソートされていて、インデックスで要素にすぐアクセスできるなら、二分探索ができます。
二分探索は、ソート済みの範囲の中央の要素と候補を比較することで範囲を半分に減らして、同じプロセスを続けます。
探索が1回だけで元のデータ構造がソートされていないなら、線形探索の方が向いています。
しかし、探索が多数回行われるなら、ソートの為の時間は探索ごとの時間削減で元が取れます。
コード：
from enum import IntEnum
from typing import Tuple, List
Nucleotide: IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))
Codon = Tuple[Nucleotide, Nucleotide, Nucleotide] # コドン型のエイリアス
Gene = List[Codon]
gene_str: str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"
def string_to_gene(s: str) -> Gene:
gene: Gene = []
for i in range(0, len(s), 3):
if(i + 2) >= len(s): #終わり。行き過ぎないこと
return gene
# 3ヌクレオチドでコドンを初期化
codon: Codon = (Nucleotide[s[i]], Nucleotide[s[i + 1]], Nucleotide[s[i + 2]])
gene.append(codon)
return gene
my_gene: Gene = string_to_gene(gene_str)
二分探索
def binary_contains(gene: Gene, key_codon: Codon) -> bool:
low: int = 0
high: int = len(gene) - 1
while low <= high: #探索空間がある間
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
acg: Codon = (Nucleotide.A, Nucleotide.C, Nucleotide.G)
gat: Codon = (Nucleotide.G, Nucleotide.A, Nucleotide.T)
my_sorted_gene: Gene = sorted(my_gene)
print(binary_contains(my_sorted_gene, acg)) #True
print(binary_contains(my_sorted_gene, gat)) #False