第54回
アルゴリズムの基礎・４～二分探索
技術コラム > 第54回 アルゴリズムの基礎・４～二分探索 > 偽金貨探しと二分探索

偽金貨探しと二分探索

さて、先のパズルでは9枚の金貨を3枚ずつ3つの組に分けました。こうすることで、探索の対象（パズルでは、1枚だけ軽い偽の金貨）を絞り込みやすくなります。同じように、たくさんのデータの中から特定の1つを見付ける場合、対象となるデータの数ができるだけ少ない方が早く見付けられます。

対象を半分にする

逐次探索は金貨を1枚ずつ量っていくのと同じで、最も手間のかかる方法です。パズルで金貨を3枚×3組に分けたことで、1回の計測でその対象が一気に3枚に絞り込めます。同じように、探索の対象となるデータ群を分割することで、一気に処理効率が向上します。　金貨は9枚だったので、3枚ずつの組に分けることができました。しかし、データの数が明らかでない場合には、必ずしも3枚の組に分ければよいというものではありません。単純に考えれば、探索の対象を常に半分(1/2)にするのが合理的です。

2つの群のうちのどちらに目指す値が含まれているかが分かれば、探索の対象は一気に1/2になります。さらに1/2になった群を1/2に絞り……と、段階的に対象を狭めていくのです。

このような探索方法を二分探索と言います。

TOP

値の整列が前提

二分探索では、探索対象のデータ群が予め整列されていることが前提となります。二分探索木の例ではランダムに並んでいる値の配列を構造体に変換して処理しましたが、ここではその過程を省略し、図2のように値が整列されて配列に格納されている状態で説明します。

この中から「24」が何番目の要素に保存されているかを調べる――という手順を考えてみましょう。


TOP

中間の添字で配列を分ける

まず、10個ある探索対象を半分に減らします。さて、どのような基準で半分にすればよいでしょう？

配列全体の中間に位置する値と探索対象の値とを比較し、探索対象の値の方が中間値より大きければ、探索対象の値は中間値より大きいはずです。その場合には、配列の中間より大きい方を次の探索対象とします。

逆に探索対象の値が中間値より小さければ、探索対象の値は中間値より小さい側に含まれているはずですから、次の探索対象は配列の中間より小さい方になります。

このような処理を次々に繰り返していけば、最後には探索対象が1つに絞り込めるはずです。

TOP

対象が半分になれば手間も半分に

例で考えてみましょう。値は11個あり、小さい方から添字が0～10となっています。中間値を保存しているのは、添字が(0+10)÷2で5となります。

添字が5の値は16です。探索対象の値である24は16より大きいので、中間値の5より大きい群に含まれているはずです。

ここで、探索対象は添字の6～10の間に絞り込めます（図3）。

半分になったデータ群の中間値は添字6と10の中間ですから、(6+10)÷2で8になります。添字8の保持している値は26で、探索対象の24より大きくなります。すると、次の探索対象は現在の中間値を示す添字8より小さい方の群になります（図4）。

最小の添字は6、最大の添字は8ですから(6+8)÷2で7が中間値となります。7の保持している値は24なので、この段階で探索対象の値が見付かりました。


図4：探索対象の値がさらに半分に減った
図4：探索対象の値がさらに半分に減った

TOP
NEXT PAGE >>

        

  

Copyright © MESCIUS inc.