トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

二分探索

[アルゴリズム]

二分探索

  概要

  • Wikipedia - 二分探索
    • 二分探索(にぶんたんさく、英: binary search、BS)や二分検索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

自作するならこんな感じか?

def ceil_index(array, l, r, key)
  while r-l > 1
    m = l + (r-l)/2
    if array[m] >= key
      r = m
    else
      l = m
    end
  end
  r
end

蟻本にあるもの

  def bsearch()
    lb,ub=0,INF
    for i in 0..100
      mid = (lb+ub)/2
      # 評価のための関数
      if C(mid)
        lb = mid
      else
        ub = mid
      end
    end
    puts "%.2f" % ub
  end
  • Rubyの場合Arrayにbsearchbsearch_indexが生えているので、コードを自分で書く必要はない

  二分探索の使いどころ

計算量オーダー

  • N = 10^5がAtCoderでよく出る最大のテストケース
    • 仮に処理のオーダーがO(N^2)になると、1秒とか2秒の制限時間を超えてしまうが
    • 処理のオーダーを縮めてO(NlogN)にすると1秒以内に間に合う
 1 秒以上かかる部分 (計算ステップ数が 108108 回を超える部分) は 「-」 で記載しています。
logN N NlogN N^2 N^3 2^N N!
2 5 12 25 130 30 120
3 10 33 100 1000 1024 3628800
4 15 59 225 3.375 32768 -
4 20 86 400 8000 1048576 -
5 25 116 625 15625 - -
5 30 147 900 27000 - -
7 100 664 10000 1000000 - -
8 300 2468 90000 27000000 - -
10 1000 9966 1000000 - - -
13 10000 132877 100000000 - - -
16 100000 1660964 - - - -
20 1000000 19931568 - - - -
お名前: コメント: