検索アルゴリズムについて

データ等の検索情報について一般的に線形検索、二分検索があります。

• 線形検索とは
  配列から１つずつ順番に合致するデータを検索します。配列がソートされている必要はありません。
  例えば配列の要素が２，０００個ある場合、最大で２，０００回の検索が必要になります。
  時間計算量は以下ようになります。

時間計算量=O(n)

• 二分検索とは
  ソート済の配列で有効な検索方法となります。配列を半分にして、検索する要素を含む半分を保持し、その配列をさらに半分にして、検査する要素をさらに半分するという流れで合致する要素が見つかるまで配列を半分にしていきます。つまり検索範囲が半分ずつになっていきます。
  時間計算量は以下ようになります

時間計算量＝O(\log n)

※時間計算量についてはビッグオー記法という記載で表現されます。
線形検索の場合、配列の要素が大きくなると検索時間も比例して大きくなります。
二分検索の場合、配列の要素が大きくなっても対数で増加するため、要素が倍になっても検索時間は倍にはなりません。

線形検索と二分検索の処理時間について

２億のデータを配列として準備し、１億と合致したら処理を終了としてます。線形検索と二分検索の処理時間を測ります。サンプルコードを記載します。

numbers = list(range(1,200000000))

def binary_search(value:int, numbers:list) -> int:
    low: int = 0
    high: int = len(numbers) - 1 
    middle:int = 0

    while( low <= high):
        middle = (low + high) // 2
        if numbers[middle] == value:
            return middle
        elif numbers[middle] < value:
            low = middle + 1
        else:
            high = middle - 1

def main(argv):
    start_time = datetime.now()
    # 線形検索
    for i in numbers:
        if 100000000 == i:
            break
    end_time = datetime.now()
    print(f"処理時間: { int((end_time - start_time).total_seconds() * 1000):,}ミリ秒")


    start_time = datetime.now()
    # 二分探索
    ret = binary_search( 100000000, numbers )
    print(f"{ret=}")
    end_time = datetime.now()
    print(f"処理時間: { int((end_time - start_time).total_seconds() * 1000)}ミリ秒")

二分検索のほうが圧倒的に早いですね。

処理時間: 11,969ミリ秒
ret=99999999
処理時間: 0ミリ秒

まとめ

線形検索と二分検索について紹介しました。
例えば、以下のようなテーブルがあり、開始値以上、終了値以下のidを取得したい場合、件数によってはDBインデックスでも検索速度には限度があるため、二分検索用のメソッドを準備する必要があります。

id	開始値	終了値
1	1	1000
2	1001	2000
・・・
1000	1000000	10000001

二分検索については業務プログラムを作成していると必ず必要となるケースが発生すると思いますので、参考にしてみてください。