バイナリサーチの簡単な紹介
バイナリサーチは名前は専門的に見えてしまうのですが、とても単純で人間らしい検索方法です。
たとえば、国語辞典で “田んぼ” を探したいとします。でも国語辞典って横から見た時に「あ」〜「ん」までのひらがなをふっていないものがありますね。
こんな感じの辞典です
そんな時はどうやって目的の「た」行を探しますか？
「た」行ってひらがなで言う真ん中の「な」行の隣だからとりあえず真ん中あたりの「な」行を探しますよね？
無事「な」行が見つかったら「た」行はその前だからその前を探す、、、と。
これがバイナリサーチなんです。まとめると。。。
- インデックスを付ける（国語辞典なら「あ」〜「ん」のこと）
- インデックス順に整列（ソート）する
- インデックスの真ん中を開けてみる
- 開けたインデックスが自分の求めているものよりも前ならさらにその真ん中を開けてみる
- 見つかるまで繰り返す
結局私たちが普段何気なくものを探しているやりかたで、機械的な分どちらかというと愚直です。