情報と知恵

情報と知恵（2）

整理・構造化

　　つぎは、蓄えるファイルへのデータの置き方の工夫で、検索効率を桁違いにあげる方法です。説明を分かりやすくするために、データをn個の数値データとします。はじめ、データはファイルにデータの生じた順に並べられています。いまデータの内容に着目して、これを値の小さい順に並べ直したとしましょう。

　　　　　　

さて、このデータを小さい順（昇順）に並べなおしたファイルでの検索を考えます。いま、検索したい指定データを　ａ　とします。探し出したいこの　ａ　は、ファイルのどこにあるか分かりません。すなわち、探索範囲はファイルの全域のn個です。いま、この探索範囲のちょうど真中のデータの値を調べてこの数値がmであることを知ったとします。すると、ファイルのデータは昇順に並んでいるので、1回のデータの調査（検索）から次のことを知ることができます。

　　　　　　a=m   のとき　　 運よく見つかった

             a>m   のとき　　 ａは真中より後ろのほうにあることが分かる

　　　　　　a<m   のとき　　 ａは真中より前のほうにあることが分かる

すなわち、見つからなかったときは、調べて得た情報mと目的のaとの関係により次の探索範囲は今回の半分に縮まります。これは２分探索法と呼ばれています。n＝1000　の場合の２分探索法による探索範囲の縮まり方は、次のようになります。

　1000→ 500→　250→　125→　63→　32→ 16→ 8→　4→　2→　1

探索範囲が1になれば見つかったことなので、２分探索法によれば1000のデータから１０回の検索で必ず見つけることができるという訳です。

一般に、n個のデータから　　回の検索でかならず目的のものへたどり着くことができます。この　　という効率は順次に調べる方法に比べて、桁外れによいものになっています。

下の図は、2分探索において、探索範囲が急速に縮まっていくことを視覚化したものです。

　

                ２分探索による範囲の縮まり方

　2分探索法の効率の良さは、探索の対象となるデータを構造化したことによるのです。バラバラであったものを目的に沿って関連付ければ、１つの情報から非常に多くの意味を取り出すことができるということです。これが相乗的に効果を生むのです。