データが見つかる例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/26 14:35 UTC 版)
下記のようなソート済み配列から25を探しだすことを考える。なお、配列内に値の重複はない（あるデータと同じ値のデータは他に存在しない）ものとする。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果欄を設け、目的のデータがあるか否か不明な部分を「?」、データを調べた上で目的のデータが無いとわかった部分を「×」、データを調べるまでもなく目的のデータが無い部分を「×」、目的のデータがあった部分を「○」にすることにする。検索前は、以下のようになる。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果? ? ? ? ? ? ? ? ? ? まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5 除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ。 中央位置の計算は、手計算では (1 + 10) / 2 でもよいが、プログラム上では 1 + (10 - 1) / 2 すなわち 最小位置 + (最大位置 - 最小位置) / 2 とした方が安全である。#実装上の間違いを参照。 位置5のデータは12なので「×」、位置1～4まではデータを調べなくても「×」とわかる。目的のデータは位置6～10にあるかもしれない。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果× × × × × ? ? ? ? ? 位置6～10の中央の位置は、6 + (10 - 6) / 2 = 8 位置8のデータは22なので「×」、位置6～7までは「×」とわかる。目的のデータは位置9～10にあるかもしれない。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果× × × × × × × × ? ? 位置9～10の中央の位置は、9 + (10 - 9) / 2 = 9 位置9のデータは25なので目的のデータが見つかったことになる。位置10は調べていないが、配列内に値の重複はないという想定なので「×」としてよい。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果× × × × × × × × ○ ×
※この「データが見つかる例」の解説は、「二分探索」の解説の一部です。
「データが見つかる例」を含む「二分探索」の記事については、「二分探索」の概要を参照ください。
- データが見つかる例のページへのリンク
