線形探索 (O(n))

並んでいる順に、当たるまで見る

名簿がバラバラの順で並んでいるとき、「田中さんはどこにいますか」に答えるには、1人ずつ名前を確かめます。下準備のない名簿では、並びに規則がないため、見ていない場所を候補から外せません。

真ん中から始めても、その左右のどちらに目的の名前があるかは分かりません。先頭から順に確かめる探し方を線形探索と呼びます。並べ替えが不要で、どんな並びにも使えます。

当たったら、その場でやめる

ここでは、最初に一致した位置を答える約束にします。位置は0から数えるので、先頭は0、次は1です。同じ値が2つあっても、最初の一致で止めます。

途中で止まる様子を、数字の表示で見てみます。break はループを抜ける命令です。

for i in range(5):
    print(i)
    if i == 2:
        break
# 出力は順に 0、1、2

2を出した時点で抜けるため、3と4は表示されません。関数の結果を返す return でも、その場で探索を終えられます。

何回比べることになるのか

名簿が佐藤、鈴木、高橋、田中の順なら、田中まで4回比べます。先頭にあれば1回、末尾ならn回、入っていない場合もn回です。最悪の増え方は O(n) で、100万件なら最大100万回になります。

必ずどこかにあり、各位置にある確率が同じなら、平均は (n + 1) / 2 回です。およそ半分でも、件数に比例するので O(n) です。平均の話には、どこにある確率を置いたかという条件が要ります。

無かったことも、結果の1つ

位置を答えるとき、「見つからなかった」の印にはよく -1 を使います。0を使うと、先頭で見つかったのか、無かったのかを区別できません。

値が同じかを比べる条件にも注意します。JavaScriptでは、文字列と数値を同一視する比較と、型も区別する比較があります。

console.log("5" == 5);   // true
console.log("5" === 5);  // false

文字列の5と数値の5を別物とするなら、下の厳密な比較を使います。

解説

数十件の配列なら、線形探索で十分な場合があります。凝った探索に必要な並べ替えの手間も含めて考えます。

例題で確かめる

商品番号が [18, 42, 7, 42, 9] と並んでいます。42を探すと、18は不一致、次の42で一致します。比較は2回、位置は1です。後ろの42まで見る必要はありません。もし55を探すなら5件すべてが不一致で、比較は5回、結果は-1になります。