はじめに
数学者であり、シンガーソングライターでもある人たちのグループに、偶然出会いました。彼らは、お気に入りの数それぞれのために歌を書いています。そして、ご想像のとおり、お気に入りの数はたくさんあります（0や73、6174など）。
お気に入りの数の歌を聴いてみたくなりましたが、あまりに多くの歌を聴き進めなければならないので、目当ての歌を見つけるにはしばらく時間がかかりそうです。幸いなことに、彼らは歌をプレイリストにまとめ、タイトル順に並べています。タイトルとは、その歌が歌っている数そのものです。
タイトルさえわかっていれば、二分探索アルゴリズムを使って歌をすばやく見つけられることに気づきます。
説明
二分探索アルゴリズムを実装してください。
二分探索アルゴリズムは、配列を半分に分割することを繰り返し、探している値が含まれる半分だけを残すことで、配列の中から目的の値を見つけ出します。
これにより、目的の値が見つかるまで、あるいは候補となる場所がすべてなくなるまで、その値がありうる場所をすばやく絞り込んでいけます。
二分探索は、配列がソートされているときにだけ使えます。
アルゴリズムは次のようなものです。
- _ソート済み_の配列の中央にある要素を見つけ、探している値と比べます。
- 中央の要素が探している値そのものであれば、それでおしまいです！
- 中央の要素が探している値より大きければ、その要素と、それより後ろにあるすべての要素を除外できます。
- 中央の要素が探している値より小さければ、その要素と、それより前にあるすべての要素を除外できます。
- 配列のすべての要素が除外されたなら、探している値は配列の中にありません。
- そうでなければ、まだ除外されていない部分の配列に対して同じ処理を繰り返します。
例を見てみましょう。
次のソート済みの配列から、数値23を探すとしましょう：[4, 8, 12, 16, 23, 28, 32]。
- まず、23を中央の要素である16と比べます。
- 23は16より大きいので、配列の左半分を除外でき、
[23, 28, 32]が残ります。
- 次に、23を新しい中央の要素である28と比べます。
- 23は28より小さいので、配列の右半分を除外できます：
[23]。
- 目的の値が見つかりました。
制限事項
Rustの標準ライブラリには、すでに二分探索の関数が用意されています。この演習では、この関数は使わず、代わりにほかの基本的な道具だけを使いましょう。
ボーナスポイント
テストは通りましたか？ コードはきれいになりましたか？ よければ、もう少し試せることもあります。
- 今の
find関数は、おそらく数値のスライスにしか使えないでしょう。しかし、Rustの型システムは十分に柔軟なので、順序を付けられる要素を持つすべてのスライスで動くfind関数を作れます。
- さらに、この
find関数はスライスだけでなく、VecやArrayでも同時に動くようにできます。
ボーナスのテストを実行するには、#[ignore]フラグを外して、次のようにgenericフィーチャーを付けてテストを実行します。
$ cargo test --features generic
ぜひ、解答へのコメントで感想を聞かせてください。この実験でコードは良くなりましたか？ 悪くなりましたか？ 何か学べることはありましたか？
