二分探索

二分探索とは、探索アルゴリズムの一種である。バイナリーサーチ(binary search)ともいう。

概要

側面に頭文字の見出しがついていない紙の英和辞典をひくときに、1ページから順番に探していく人はいない。たいていは、真ん中あたりの適当なページを開いて、目的の単語より前であればそのページより前の部分を除外し、目的の単語より後であればそのページより後ろを除外するという作業を繰り返して範囲を絞っていくという方法を取る。

このように、順序付けされたリストから目的のものを探しだす時に、対象を二分割して目的のものを含まない方を除外していく探索法を二分探索という。

その効率はO(log n)で表され、1000ページの本でも10回の操作で1ページ以内に絞ることが出来、たとえ100万ページの本であったとしてたった20回の操作で1ページ以内に絞ることが出来る。単純な割に非常に強力なアルゴリズムとして知られている。

応用例

「ニコニコ大百科の読者が、一覧の一覧の編集履歴から、「ストーリーを一行で語るの一覧」が追加された日付を調べる手順」について検討してみる。

一覧の一覧の編集履歴は2016年8月末日現在で、800件以上の履歴が存在しており、一件一件を調べていこうとすると非常に骨の折れる作業になる。

以下のように応用すれば効率的に探し当てることができる。

1. まず、800件の半分あたりで400件目近くと思われるページを開く。ニコニコ大百科の仕様上、履歴は30件毎に区切って表示されるので391件目を開いた。
2. ページに「ストーリーを一行で語るの一覧」が存在するかページ内検索する → 存在するので、追加されたのはそれ以前ということになる。
3. 次に400件目と800件目の中間くらいということで、600件目近くと思われるページを開く。601件目を開いた。
4. 同様にページ内検索 → 存在する。
5. 次は600件目と800件目の中間くらいということで、700件目近くと思われるページを開く。691件目を開いた。
6. 同様にページ内検索 → 存在する。
7. 次は700件目と800件目の中間くらいということで、750件目近くと思われるページを開く。751件目を開いた。
8. 同様にページ内検索 → 存在しない。これで「ストーリーを一行で語るの一覧」が追加されたリビジョンが691件目から751件目の間に存在することが確定した。
9. 次は691件目と751件目の中間くらいということで、721件目を開く。
10. 同様にページ内検索 → 存在する。
11. 次は721件目と751件目の中間くらいということで、735件目を開く。
12. 同様にページ内検索 → 存在しない。
13. 次は721件目と735件目の中間くらいということで、728件目を開く。
14. 同様にページ内検索 → 存在する。
15. 次は728件目と735件目の中間くらいということで、731件目を開く。
16. 同様にページ内検索 → 存在しない。
17. 次は728件目と731件目の間ということで、730件目を開く。
18. 同様にページ内検索 → 存在しない。
19. 次は728件目と730件目の間ということで、729件目を開く。
20. 同様にページ内検索 → 存在する。
21. 以上から「ストーリーを一行で語るの一覧」は730件目から729件目になるときに追加されたことが分かる。編集履歴から日付は2008年8月10日と分かる。

(注: 上記〜件目というのは2016年9月4日現在の値です。)

本例がアルゴリズムとして厳密さに欠けるという批判はもっともであるが、現実への応用にはこれくらいの柔軟性は必要である。

関連動画

関連商品

関連項目

• アルゴリズム
• 検索
• リスト
• ソート
• 動的計画法