二分探索
2006.03.16 23:06 探索
管理されたデータセットは、ほとんどの場合、整列されています。「整列されたデータ」は探索(検索)しやすいのです。
二分探索は、データの探索キーの大小関係を利用して、高速なデータ探索を可能にします。ここで重要なことは、「データが探索キーによって順番に整列されている」場合に限り、二分探索が適用できます。例えば、以下の「生徒名簿」について考えてみましょう。
この生徒名簿では、「学籍番号」を探索キーとすれば、二分探索が適用できます。なぜなら「学籍番号」が昇順に整列されているからです。しかし、例えば「名前」を探索キーとした場合は、二分探索が適用できません。
二分探索の原理はとても簡単です。データが1次元の配列に格納されているとします。
探索の範囲が半分になっていくので、高速な探索になります。
see-try-see
二分探索のプログラムです。
探索の範囲を指定する変数 left と right 、探索範囲の中央を指定する変数 mid を用意します。left は探索の左端のデータを指し示し、right は右端 + 1 のデータを指し示します。二分探索は最初データセット全体を探索の範囲とするので、left を 0 に、right をデータセットのサイズ size に設定します。
012 行目の while ループで、現時点の探索範囲のまん中のインデックス mid が指し示す値と key とを比較してチェックしていきます。もし、値が一致しているならば、mid を返します。mid が指し示す値が key よりも大きいならば、目的の値は mid よりも前半部分にある可能性がある(後半にはない)ので、right を mid とすることで探索範囲を前半部分に設定します。逆の場合は、left を mid + 1 とすることで後半部分に設定します。ループの繰り返し条件である left < right は、探索範囲がまだ存在することを示し、もし探索範囲がなくなってしまったら、key が発見できなかったとして-1を返します。
二分探索は、データの探索キーの大小関係を利用して、高速なデータ探索を可能にします。ここで重要なことは、「データが探索キーによって順番に整列されている」場合に限り、二分探索が適用できます。例えば、以下の「生徒名簿」について考えてみましょう。
学籍番号 | 名前 | 年齢 | 学科 |
---|---|---|---|
1110171 | Nuno | 21 | ソフト |
1120085 | Dai | 21 | ソフト |
5101113 | nobe | 22 | 情報 |
8061103 | fuku | 26 | 情報システム |
8071201 | Sato | 26 | コンピュータ |
この生徒名簿では、「学籍番号」を探索キーとすれば、二分探索が適用できます。なぜなら「学籍番号」が昇順に整列されているからです。しかし、例えば「名前」を探索キーとした場合は、二分探索が適用できません。
二分探索の原理はとても簡単です。データが1次元の配列に格納されているとします。
1. 最初はデータセット全体を探索の範囲とする
2. 探索の範囲中のまん中の要素を調べる
3. 目的の要素とまん中の要素が一致すれば終了
4. 目的の値が、まん中の値よりも小さければ前半部分を、大きければ後半部分を探索の範囲として2へ戻る
2. 探索の範囲中のまん中の要素を調べる
3. 目的の要素とまん中の要素が一致すれば終了
4. 目的の値が、まん中の値よりも小さければ前半部分を、大きければ後半部分を探索の範囲として2へ戻る
探索の範囲が半分になっていくので、高速な探索になります。
二分探索のプログラムです。
探索の範囲を指定する変数 left と right 、探索範囲の中央を指定する変数 mid を用意します。left は探索の左端のデータを指し示し、right は右端 + 1 のデータを指し示します。二分探索は最初データセット全体を探索の範囲とするので、left を 0 に、right をデータセットのサイズ size に設定します。
012 行目の while ループで、現時点の探索範囲のまん中のインデックス mid が指し示す値と key とを比較してチェックしていきます。もし、値が一致しているならば、mid を返します。mid が指し示す値が key よりも大きいならば、目的の値は mid よりも前半部分にある可能性がある(後半にはない)ので、right を mid とすることで探索範囲を前半部分に設定します。逆の場合は、left を mid + 1 とすることで後半部分に設定します。ループの繰り返し条件である left < right は、探索範囲がまだ存在することを示し、もし探索範囲がなくなってしまったら、key が発見できなかったとして-1を返します。
スポンサーサイト
| コメント(3) | トラックバック(0) | ↑ページトップ |