二分探索単語

ニブンタンサク

  • 3
  • 0
掲示板をみる(4)
  • twitter
  • facebook
  • はてな
  • LINE
  • ほめる(3)
  •  
  •  
  •  
  •  
  • その他

二分探索とは、探索アルゴリズムの一種である。バイナリーサーチ(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日現在の値です。)

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

関連動画

関連商品

関連項目

この記事を編集する

掲示板

  • 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)かかるというところ
    (ソート済みかわからない場合は先頭から順に見たほうがい)

おすすめトレンド

急上昇ワード改

最終更新:2020/09/28(月) 06:00

ほめられた記事

最終更新:2020/09/28(月) 06:00

スマホで作られた新規記事

ウォッチリストに追加しました!

すでにウォッチリストに
入っています。

OK

追加に失敗しました。

OK

追加にはログインが必要です。

           

ほめた!

すでにほめています。

すでにほめています。

ほめるを取消しました。

OK

ほめるに失敗しました。

OK

ほめるの取消しに失敗しました。

OK

ほめるにはログインが必要です。

タグ編集にはログインが必要です。

タグ編集には利用規約の同意が必要です。

TOP