BinSearch(二分探索)

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

ここで,666がどこにあるか,左から線形探索で探すと......8回目に見つけることができますね.しかし,もっとはやく見つけ出す方法はないのでしょうか?その1つの方法として,二分探索があります.二分探索は,

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

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

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