BinSearch(二分探索)
以下のように整列(ソート)されている配列データを考えます。
ここで,666がどこにあるか,左から線形探索で探すと......8回目に見つけることができますね.しかし,もっとはやく見つけ出す方法はないのでしょうか?その1つの方法として,二分探索があります.二分探索は,
- ソーティングされているデータを対 象とする
- 検索対象の中央(メディアン)に位置するデータと比較 し,検索対象を左右のどちらかに絞り込んで検索を繰り返す.
というアルゴリズムです.
補足:データ数が偶数の場合は,厳密なメディアの位置が定まりませんので,その前後をメディアンをするようにしましょう. 例えば,データが10個あった場合,そのメディアン値は,4.5個目となります.そのときは,メディアンを4または5に設定します.