サーチアルゴリズム

CS50 2019課を聞いて内容を整理するシリーズの文章

学習目標

指定した配列で特定の値を検索する方法を説明します.

キーワード

線形探索

バイナリ検索

レッスン内容

配列とは?

1つのデータ型の複数の値がメモリに集中する構造.
コンピュータは、これらの値にアクセスすると、配列内の各インデックスにアクセスします.
配列に属する値を決定するには、線形検索、バイナリ検索の方法を使用します.

1.線形検索

配列のインデックスを最初から最後まで増やして、値が値に属しているかどうかを確認する方法.
電話帳を例にとると、欲しい人の番号を見つけるために、順番に
簡単にpythonコードで次のように表します.

def linear_search(value, array):
    for i in array:
        if i == value:
            return True
    return False

2.バイナリ検索

バイナリ検索は、チェックする配列がソートされている場合にのみ使用できます.
方法は、配列の中間インデックスから開始し、検索する値と比較し、より小さいインデックスまたはより大きいインデックスに繰り返し移動します.
簡単にpythonコードで次のように表します.

def binary_search(value, array):
    first, last = 0, len(array)
    
    while first < last:
        mid = (first+last) // 2
        if value == array[mid]:
            return True
        elif value < array[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False

考える

ソートされていない配列がある場合は、線形検索が速いですか、バイナリ検索が速いですか。

ソートされていない場合は、バイナリ検索は使用できません.
バイナリ検索は配列の中間インデックスをチェックして左右方向を決定する必要があります.ソートがなければ方向を判断できないからです.
したがって,この問題の答えが高速であっても,線形検索しか使用できない.