二分探索単語

ニブンタンサク

二分探索とは、探索アルゴリズムの一種である。バイナリーサーチ(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. 次は691751件の中間くらいということで、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日現在の値です。)

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

関連動画

関連商品

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

二分探索

1 ななしのよっしん
2017/01/02(月) 22:59:48 ID: dd9CS9lgLl
アルゴリズムから飛んできたけれど、なかなかに面い解説する記事だな
ニコニコ大百科編集履歴で説明するのもニコニコ大百科らしくて割りと好き
2 ななしのよっしん
2017/08/19(土) 18:49:21 ID: RX+p7lMNFl
ピタゴラスイッチで紹介されてたな
手順だけ見ると何回も同じことやって面倒くさそうだけど辞書引くときはみんな自然にやってることってのが面
3 強盗
2017/08/20(日) 07:24:29 ID: 4HLpyZURla
いいぞ
アルゴリズム関連の記事増えろ
4 ななしのよっしん
2017/09/12(火) 14:29:23 ID: M0141PW33E
二分探索すごいのは記事にもあるけど
要素が倍に増えても計算量が1回分しか増えないところ

二分探索厄介なのは前提条件になるソート済みデータを作るために
結局O(n logn)かかるというところ
(ソート済みかわからない場合は先頭から順に見たほうがい)