スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




二分探索

2006.03.16 23:06  探索

管理されたデータセットは、ほとんどの場合、整列されています。「整列されたデータ」は探索(検索)しやすいのです。

二分探索は、データの探索キーの大小関係を利用して、高速なデータ探索を可能にします。ここで重要なことは、「データが探索キーによって順番に整列されている」場合に限り、二分探索が適用できます。例えば、以下の「生徒名簿」について考えてみましょう。

学籍番号 名前 年齢 学科
1110171 Nuno 21 ソフト
1120085 Dai 21 ソフト
5101113 nobe 22 情報
8061103 fuku 26 情報システム
8071201 Sato 26 コンピュータ

この生徒名簿では、「学籍番号」を探索キーとすれば、二分探索が適用できます。なぜなら「学籍番号」が昇順に整列されているからです。しかし、例えば「名前」を探索キーとした場合は、二分探索が適用できません。

二分探索の原理はとても簡単です。データが1次元の配列に格納されているとします。

1. 最初はデータセット全体を探索の範囲とする
2. 探索の範囲中のまん中の要素を調べる
3. 目的の要素とまん中の要素が一致すれば終了
4. 目的の値が、まん中の値よりも小さければ前半部分を、大きければ後半部分を探索の範囲として2へ戻る

探索の範囲が半分になっていくので、高速な探索になります。

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を返します。



スポンサーサイト

| コメント(3) | トラックバック(0) | ↑ページトップ |




線形探索(2)

2006.03.16 22:44  探索

単純な線形探索よりも効率の良い線形探索のアルゴリズムを考えます。繰り返しになりますが、単純な線形探索のプログラムでは、

  1. index < size: indexがデータの末尾を越えていないかのチェック
  2. data[ index ] == key : indexが指すデータの中身が目的の値でないかのチェック

の2つをチェックしなければなりませんでした。これから考えるアルゴリズムでは、データに「番兵」と呼ばれる特別な値を設置することによって、比較演算の回数を半減させます。下図は整数のデータが格納された配列から与えられた値を探索している様子を示しています。
linearSearch2.gif


この例でも、要素数が12個の配列の中から8を探していて、配列の先頭から順番に各要素が8であるかどうかをチェックしています。重要なポイントは、データの末尾に番兵として目的の値である8を追加していることです。番兵を設置することによってデータの中に目的の値が存在することが保障されるので、探索している範囲がデータ数を超えてしまわないかのチェックを行う必要がなくなります。目的のデータが見つかったときの index がデータのサイズを超えていた場合(index が size と等しい場合)、それは番兵を示すので、データに目的の値が存在しなかったことを示します。番兵を用いた線形探索のプログラムの例を以下に示します。



09 行目でデータの末尾に番兵である key を設置します。その結果、メインループでの比較処理はdata[ ++index ] != key の1つしかありません。番兵がいるのでメインループの while( data[ ++index ] != key ); は必ず終了することが保障されます。つまり、データの範囲を超えてチェックしていまうという危険な処理を"番兵"が阻止します。メインループが終了した時の index の値が、目的の値を指します。データが見つからなかった場合は、index が番兵にたどりついてしまった場合、すなわち index が size に達してしまった場合です。

| コメント(0) | トラックバック(0) | ↑ページトップ |




線形探索(1)

2006.03.16 18:24  探索

線形探索は最も単純で効率の悪いアルゴリズムと言えます。このアルゴリズムは、データセットの先頭から順番にデータを調べていきます。下の図は、整数のデータが格納された配列から、「与えられた値」を探索している様子を示しています。この例では、要素数が12個の配列の中から「8」という数字を、配列の先頭から順番に探しています。目的のデータが見つかったときに処理が終了します。
linearSearch1.gif

このアルゴリズムはデータがどのような順番で配置されていても、データセットの中に目的のデータがあれば、正確にその要素を取得することができます。線形探索を実装したプログラムの例を以下に示します。


プログラムは非常に単純で、for ループを用いて、データの先頭から末尾まで調べていき、目的のデータが発見された時点で、そのインデックスを結果として返しています。見つからなかった場合は、特別な値として-1を返します

少し効率がよくなる実装方法。

| コメント(1) | トラックバック(0) | ↑ページトップ |




探索

2006.03.16 18:24  探索

たくさんのデータが蓄えられているデータセットの中から、目的のデータを探し出す方法を考えてみましょう。問題を単純にするために、配列から、ある要素を探し出すアルゴリズムを考えます。

| コメント(0) | トラックバック(0) | ↑ページトップ |

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。