はじめに
数学者であり、シンガーソングライターでもある人たちのグループに、偶然出会いました。彼らは、お気に入りの数それぞれのために歌を書いています。そして、ご想像のとおり、お気に入りの数はたくさんあります（0や73、6174など）。
お気に入りの数の歌を聴いてみたくなりましたが、あまりに多くの歌を聴き進めなければならないので、目当ての歌を見つけるにはしばらく時間がかかりそうです。幸いなことに、彼らは歌をプレイリストにまとめ、タイトル順に並べています。タイトルとは、その歌が歌っている数そのものです。
タイトルさえわかっていれば、二分探索アルゴリズムを使って歌をすばやく見つけられることに気づきます。
説明
二分探索アルゴリズムを実装してください。
二分探索アルゴリズムは、配列を半分に分割することを繰り返し、探している値が含まれる半分だけを残すことで、配列の中から目的の値を見つけ出します。
これにより、目的の値が見つかるまで、あるいは候補となる場所がすべてなくなるまで、その値がありうる場所をすばやく絞り込んでいけます。
二分探索は、配列がソートされているときにだけ使えます。
アルゴリズムは次のようなものです。
- _ソート済み_の配列の中央にある要素を見つけ、探している値と比べます。
- 中央の要素が探している値そのものであれば、それでおしまいです！
- 中央の要素が探している値より大きければ、その要素と、それより後ろにあるすべての要素を除外できます。
- 中央の要素が探している値より小さければ、その要素と、それより前にあるすべての要素を除外できます。
- 配列のすべての要素が除外されたなら、探している値は配列の中にありません。
- そうでなければ、まだ除外されていない部分の配列に対して同じ処理を繰り返します。
例を見てみましょう。
次のソート済みの配列から、数値23を探すとしましょう：[4, 8, 12, 16, 23, 28, 32]。
- まず、23を中央の要素である16と比べます。
- 23は16より大きいので、配列の左半分を除外でき、
[23, 28, 32]が残ります。
- 次に、23を新しい中央の要素である28と比べます。
- 23は28より小さいので、配列の右半分を除外できます：
[23]。
- 目的の値が見つかりました。
例外メッセージ
例外を発生させる必要がある場合もあります。そのときは、エラーの原因が何であるかを示す意味のあるエラーメッセージを必ず含めるようにしましょう。こうするとコードが読みやすくなり、デバッグもずっと楽になります。エラーの原因がある特定の型であるとわかっている場合は、組み込みのエラータイプの中から1つを選んで発生させることもできますが、その場合でも意味のあるメッセージを含めるようにしましょう。
この演習では、与えられた値が配列の中に見つからないときに、raise文を使ってValueErrorを「投げる」必要があります。exceptionをraiseし、それにメッセージを添えたときだけ、テストは通ります。
メッセージ付きでValueErrorを発生させるには、メッセージをexception型の引数として書きます。
# example when value is not found in the array.
raise ValueError("value not in array")
