【Python】二分探索

この記事は、オライリー社の書籍「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

 

返信を残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください