二分探索

以下のように整列(ソート)されている配列データを考えます。

111
123
222
333
444
456
555
666
777
789

ここで,666がどこにあるか,線形探索で探すと......8回目に見つけることができますね.

しかし,もっとはやく見つけ出す方法はないのでしょうか?その1つの方法として,二分探索があります.

二分探索は,

ソーティングされているデータを対 象とする
検索対象の中央(メディアン)に位置するデータと比較 し,検索対象を左右のどちらかに絞り込んで検索を繰り返す.

というアルゴリズムです.

補足:データ数が偶数の場合は,厳密なメディアの位置が定まりませんので,その前後をメディアンをするようにしましょう. 例えば,データが10個あった場合,そのメディアン値は,4.5個目となります.そのときは,メディアンを4または5に設定します.

例)検索過程

例として,666を探してみましょう.全部のデータ数が10個のため,6番目(456)をメディアンとします.

<-------------------------------------------------------------------------->
LEFT        
456
      RIGHT

666は456より大きいので,右側を範囲とします.

 
<--------------------------->
            LEFT    
  RIGHT

全部のデータ数が4個のため,3番目(777)をメディアンとします.

 
<--------------------------->
            LEFT  
777
RIGHT

666は777より大きいので,左側を範囲とします.

 
<----->
   
            LEFT RIGHT
777
 

全部のデータ数が2個のため,2番目(666)をメディアンとします.見つかったので終了です.

     
              666


Comments