線形探索

探しものを先頭から順に見る

前章までで配列とデータ構造の扱い方を身につけました。ここからは、その上で動く定番アルゴリズムに入ります。科目Bの擬似言語問題では、探索と整列が毎回のように顔を出します。しかも「答えの値」ではなく「途中経過」を聞かれるため、動きを丸暗記した人ほど取りこぼします。1行ずつ追える力がそのまま得点になる分野です。

最初は線形探索です。配列の先頭から順に1つずつ見ていき、探している値と同じものが見つかったらそこで止める、という素朴な方法です。素朴ですが、データが並んでいなくても使えるという強みがあります。後で学ぶ二分探索は、あらかじめ昇順に並んでいることが前提になります。この前提の差が、試験でどちらを選ぶかの分かれ目になります。

擬似言語で書くとこうなります

kaisu は、値をいくつ調べたかを数える変数です。for の中に入るたびに1ずつ増やしているので、比較した回数と一致します。見つからずに for を抜けきったときは -1 を返します。この「見つからなかったときの戻り値」は問題でよく穴埋めにされるので、意味を持った値を返している点に注目してください。

比較回数はどう決まるか

線形探索の比較回数は、探している値が何番目にあるかでそのまま決まります。先頭にあれば1回、末尾にあれば要素数と同じ回数です。見つからない場合は最後まで見るので、要素数と同じ回数になります。

では平均は何回でしょうか。データが必ずどこかにあり、どの位置にある確率も等しいとすると、1回から n 回までの平均なので (n + 1) ÷ 2 回です。要素数が 100 なら約 50 回、1000 なら約 500 回で、要素数に比例して増えます。これを後の回で O(n) と表します。

試験でのつまずきどころ

つまずきやすいのは、return が for の途中にあるという構造です。見つかった瞬間に関数そのものが終わるので、その後ろの行は実行されません。「for を最後まで回る」と思い込むと、比較回数を要素数と答えてしまいます。

もう1つは、比較回数と繰返し回数を混同することです。上のコードでは、比較の直前に kaisu を増やしているので両者が一致します。しかし増やす位置が if の後ろに移ると、結果が1ずれます。数える行がどこに置かれているかを必ず自分の目で確かめてください。

それではトレースで、5個の配列から値を探す様子を追いましょう。

1. 各行を実行したあとの値を入れる
2. 値が変わらない変数はそのままの値を入れる
3. まだ値が入っていない変数は — を入れる