26.1.6.19 二分探索

一列に並んでいるデータの値を調べることを考えましょう．たとえば英単語を辞書で引く場合などがそうです．この時，データがあるきめられた順番で並んでいると，非常に速く調べることができます．辞書の"A"，"B"，"C"などの見出しも，単語がアルファベット順に並んでいるので役立っているのです．

データが順番に並べられている時に探索を高速化する方法としては，この見出し(index)を使う方法と，調べる範囲を半分々々にしてゆく2分探索(binary search)とが代表的です．2分探索の要領は次のとおりです．

• 調べる範囲の下限(low)と上限(high)とを決める．

• high <= low となるまで以下を繰り返す．

• 範囲の中間点(mid)を(low+high)/2で求める．

• midの位置の要素値を目的の値と比較する．

• 目的値の方が大きい場合，low=mid+1とする．
  

上半分を残したことになる．

• 目的値の方が小さい場合，high=mid-1とする．
  

下半分を残したことになる． これをプログラムの形に直すのは簡単ですね．また，目的値が存在しない場合に，どのようになって停止するかについても考えてみて下さい．

調べる範囲が急速に小さくなってゆくこの方法では，データ全体の個数をnとするとき，log2n程度の繰返しで答が求まります．たとえばn=1000でも10回程度で求まる，高速な方法です．