二分探索
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量は O ( log 2  n ) {\displaystyle O(\log _{2}n)} である(O記法)。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。
下記のようなソート済み配列から4を探しだすことを考える。なお、配列内に値の重複はないものとする。
まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5
(除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ)
位置5のデータは12なので「×」、位置6~10まではデータを調べなくても「×」とわかる。目的のデータは位置1~4にあるかも知れない。
位置1~4の中央の位置は、1 + (4 - 1) / 2 = 2
位置2のデータは3なので「×」、位置1も「×」とわかる。目的のデータは位置3~4にあるかも知れない。
位置3~4の中央の位置は、3 + (4 - 3) / 2 = 3
位置3のデータは5なので「×」。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。