データが見つからない例(1)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/26 14:35 UTC 版)
「二分探索」の記事における「データが見つからない例(1)」の解説
下記のようなソート済み配列から4を探しだすことを考える。なお、配列内に値の重複はないものとする。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 まず、配列の中央の位置を求めると、1 + (10 - 1) / 2 = 5 （除算の端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ） 位置5のデータは12なので「×」、位置6～10まではデータを調べなくても「×」とわかる。目的のデータは位置1～4にあるかも知れない。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果? ? ? ? × × × × × × 位置1～4の中央の位置は、1 + (4 - 1) / 2 = 2 位置2のデータは3なので「×」、位置1も「×」とわかる。目的のデータは位置3～4にあるかも知れない。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果× × ? ? × × × × × × 位置3～4の中央の位置は、3 + (4 - 3) / 2 = 3 位置3のデータは5なので「×」。もし、データ4が存在するならば、位置3のデータ5より小さいので左になるはずである。しかし、すでにそこには存在しないことがわかっている。また、位置3より右である位置4は、データを調べていないが、位置3より大きなデータのはずなので「×」。以上でデータが見つからないという結果になる。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 結果× × × × × × × × × ×
※この「データが見つからない例(1)」の解説は、「二分探索」の解説の一部です。
「データが見つからない例(1)」を含む「二分探索」の記事については、「二分探索」の概要を参照ください。
データが見つからない例(2)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/26 14:35 UTC 版)
「二分探索」の記事における「データが見つからない例(2)」の解説
下記のようなソート済み配列から29を探しだすことを考える。なお、配列内に値の重複はないものとする。 位置12345678910データ1 3 5 11 12 13 17 22 25 28 データの全体の一番右側が29より小さいので、データが見つからないという結果になる。
※この「データが見つからない例(2)」の解説は、「二分探索」の解説の一部です。
「データが見つからない例(2)」を含む「二分探索」の記事については、「二分探索」の概要を参照ください。
- データが見つからない例のページへのリンク
