二分探索

説明

二分探索アルゴリズムを実装してください。

二分探索アルゴリズムは、配列を半分に分割することを繰り返し、探している値が含まれる半分だけを残すことで、配列の中から目的の値を見つけ出します。 これにより、目的の値が見つかるまで、あるいは候補となる場所がすべてなくなるまで、その値がありうる場所をすばやく絞り込んでいけます。

アルゴリズムは次のようなものです。

• _ソート済み_の配列の中央にある要素を見つけ、探している値と比べます。
• 中央の要素が探している値そのものであれば、それでおしまいです！
• 中央の要素が探している値より大きければ、その要素と、それより後ろにあるすべての要素を除外できます。
• 中央の要素が探している値より小さければ、その要素と、それより前にあるすべての要素を除外できます。
• 配列のすべての要素が除外されたなら、探している値は配列の中にありません。
• そうでなければ、まだ除外されていない部分の配列に対して同じ処理を繰り返します。

例を見てみましょう。

次のソート済みの配列から、数値23を探すとしましょう：[4, 8, 12, 16, 23, 28, 32]。

• まず、23を中央の要素である16と比べます。
• 23は16より大きいので、配列の左半分を除外でき、[23, 28, 32]が残ります。
• 次に、23を新しい中央の要素である28と比べます。
• 23は28より小さいので、配列の右半分を除外できます：[23]。
• 目的の値が見つかりました。

---

出典

Wikipedia