二分探索

二分探索とは

二分探索（にぶんたんさく、BS;Binary Search）とは検索のアルゴリズムの一つ。二分検索、バイナリサーチともいう。
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、
中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量は<math>O(\log_2 n)</math>である（O記法）。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。

• 出典: フリー百科事典『ウィキペディア（Wikipedia）』
• [ 二分探索の改定履歴 ]