二分探索
下記のようなソート済み配列から25を探しだすことを考える。なお、配列内に値の重複はない(あるデータと同じ値のデータは他に存在しない)ものとする。
結果欄を設け、目的のデータがあるか否か不明な部分を「?」、データを調べた上で目的のデータが無いとわかった部分を「×」、データを調べるまでもなく目的のデータが無い部分を「×」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。
まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5
除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ。
中央位置の計算は、手計算では (1 + 10) / 2 でもよいが、プログラム上では 1 + (10 - 1) / 2 すなわち 最小位置 + (最大位置 - 最小位置) / 2 とした方が安全である。#実装上の間違いを参照。
位置5のデータは12なので「×」、位置1~4まではデータを調べなくても「×」とわかる。目的のデータは位置6~10にあるかもしれない。
位置6~10の中央の位置は、6 + (10 - 6) / 2 = 8
位置8のデータは22なので「×」、位置6~7までは「×」とわかる。目的のデータは位置9~10にあるかもしれない。
位置9~10の中央の位置は、9 + (10 - 9) / 2 = 9
位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、配列内に値の重複はないという想定なので「×」としてよい。