第二の巻 線形探索

初段 / 目安 15分

師範が二つめの巻物を開きます。「会員番号の帳簿から、目当ての番号を探せ。見つけた位置と、何回比べたかも報告せよ」

「何回比べたか」まで求められるのが、この巻物の妙なところです。答えが合っていればよいのではなく、そこにたどり着くまでに何手かかったかを自分で数えさせる。師範がわざわざそう書いたのには理由がありますが、それは第四の巻まで伏せておきます。

帳簿は先頭から順に並んでいます。あなたのやることは、人が指で追うのと同じです。1件見て、違ったら次を見る。それだけです。

完成条件

会員番号の配列と、探したい番号を受け取り、見つけた位置と比較回数を1つの文字列にして返す関数 linearSearch を作ってください。どの言語で解く場合も、関数名は linearSearch にしてください。

返す文字列の形は次のとおりです。位置は先頭を 0 とする番号です。

• 最後まで見つからなかったときは、位置を -1 にします。比較回数は最後まで数えた回数です
• 「位置」「/」「比較」「回」の前後の半角スペースまで一致させること
• 配列には必ず1つ以上の要素が入っています

数え方の約束

比較回数は、帳簿の1件と目当ての番号を照らし合わせた回数です。1件目を見た時点で 1 回、2件目を見た時点で 2 回になります。見つけたらそこで打ち切り、それ以降は数えません。

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

見つけたあとも配列の最後までループを回してしまうと、比較回数が合いません。見つけた瞬間に打ち切る書き方を、自分の言語で確かめてから始めてください。

1. 関数名は linearSearch。どの言語で解く場合も同じ名前にすること
2. 先頭から順に1件ずつ照らし合わせること
3. 照らし合わせた回数を数え、見つけたらそこで打ち切ること
4. 見つからなかったときは位置を -1 にすること
5. 「位置 3 / 比較 4回」の形の文字列を1つ返すこと。印字ではなく return で返す