第四の巻 二分探索

中段 / 目安 25分

四つめの巻物。師範は開く前に、こう前置きしました。「第二の巻で、なぜ比較回数まで数えさせたと思う。……布石よ」

巻物にはこうあります。「並んだ帳簿なら、真ん中から攻められる。low と high の二本の指で、範囲を半分ずつ潰せ。第二の巻と比較回数を比べてみよ」

第二の巻の帳簿は、実はもともと小さい順に並んでいました。並んでいる帳簿を先頭から1件ずつなぞるのは、五十音順の辞書を1ページ目からめくるのと同じです。真ん中を開けば、探している語が前半にあるか後半にあるかが一度で分かります。分かった時点で、もう半分は見なくてよくなります。

完成条件

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

返す文字列の形は、第二の巻と同じです。位置は先頭を 0 とする番号です。

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

数え方の約束

比較回数は、真ん中の1件を目当ての番号と照らし合わせた回数です。範囲を1回狭めるごとに 1 回増えます。等しいか、小さいか、大きいかを見るのは、まとめて 1 回と数えます。

比べてみよ

8件の帳簿から 1150 を探すと、第二の巻は 4 回、この巻は 1 回です。見つからない 1200 を探すと、第二の巻は 8 回、この巻は 3 回で「無い」と言い切れます。件数が増えるほど差は開き、1万件なら線形探索の1万回に対して、二分探索は14回で済みます。

進め方

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

二分探索でいちばん間違えやすいのは、範囲の狭め方です。真ん中を mid としたとき、次の範囲に mid 自身を含めてしまうと、範囲が狭まらず永遠に終わりません。

1. 関数名は binarySearch。どの言語で解く場合も同じ名前にすること
2. low と high で範囲を持ち、真ん中と比べて範囲を半分に狭めること
3. 真ん中と照らし合わせた回数を数えること
4. 見つからなかったときは位置を -1 にすること
5. 「位置 3 / 比較 1回」の形の文字列を1つ返すこと。印字ではなく return で返す