さがす——まっすぐに

よみもの＋手を動かす時間：およそ20分

いちばん正直なさがし方

ロッカーの番号札が10枚、ならんでいます。この中に「42」はあるでしょうか。

なにも工夫しないなら、手順はひとつです。先頭から1つずつ、順にくらべる。この手順は「まっすぐさがす」——線形探索（せんけいたんさく）と呼ばれます。再生して、くらべた回数を見てください。

数列（コンマ区切りで打ちかえられます）探し物

まっすぐさがすくらべた回数 1

381421304257687591

1番目は 3。42 ではない

1 / 6 場面

42は6番目にいたので、6回で見つかりました。地味ですが、この手順には良いところがあります。数列がどんな順番でも働くこと、そして手順として完璧に曖昧さがないことです。

探し物の欄を打ちかえて、遊んでみてください。「3」をさがすと1回で終わります。「91」なら10回かかります。

同じ手順なのに、回数は探し物の居場所しだいで変わる——そこで手順を測るときは、場合を分けて考えます。

手順の力くらべでふつう使うのは、最悪の場合です。「最悪でもこれだけで済む」は約束にできますが、「運がよければ1回」は約束になりません。

今度は、探し物を「50」にしてみてください。数列のどこにもない数です。

10回くらべて、ようやく「ありません」が出ました。ここに、まっすぐさがす手順のいちばん重い性質があります。「ない」と言い切るには、ぜんぶ見るしかないのです。1枚でも見残しがあれば、「そこにあったかもしれない」が消えません。誠実に「ない」と言うことは、見つけることより高くつきます。

ロッカーが10枚なら最悪10回。1,000枚なら最悪1,000回。10,000枚なら——もう言えますね。

まっすぐさがす手順の手間は、数列の長さにそのまま比例します。長さが10倍になれば、手間も10倍。このコースではこれを、手順のかたちと呼ぶことにします。グラフに描けばまっすぐな直線になる、素直なかたちです。あとのレッスンで、もっと急なかたちや、おどろくほど平らなかたちが出てきます。

✎ 演習：最悪をつくる

実験室の数列と探し物を打ちかえて、次の2つを作ってください。

ヒント1（考え方）

1回で終わるのは、探し物がどこにいるときでしょう。最大になるのは「いちばん奥にいる」と、もうひとつ——見つからずに終わる場合を思い出してください。

こたえ

1は先頭の数（はじめの数列なら3）をさがすとき。2は末尾の数（91）をさがすときと、どこにもない数（たとえば50）をさがすとき——どちらも10回です。「最後にいる」と「いない」が同じ値段だというのは、ぜんぶ見ないと「ない」と言えないからです。