コンテンツにスキップ

二分探索のリンク集

二分探索について、参考になる記事や資料をまとめました。

二分探索は、答えの候補が並んでいて、ある境目より手前では条件を満たさず、そこから先ではずっと満たす(単調性がある)ときに、その境目を O(log⁡N)O(\log N) 回の判定で求める手法です。ソート済みの配列から値を探すのが基本の形で、C++ の std::lower_bound や Python の bisect がこれにあたります。

競プロでよく使うのは、その一般化です。「答えを xx 以下にできるか」のような判定問題が xx について単調なら、答えそのものを二分探索で求められます(答えで二分探索)。最小値の最大化・最大値の最小化や、平均値の最大化がこの形の典型です。実数の範囲でも同じように探せますが、打ち切り方に注意が必要です。

実装では、条件を満たす側の端を ok、満たさない側の端を ng として、ok と ng が隣り合うまで真ん中で区切る書き方(めぐる式二分探索)がよく使われます。範囲が大きいときは、真ん中を (ok + ng) / 2 で計算すると和が型の範囲を超えることがあるので、ok + (ng - ok) / 2 のように書くと安全です。

セグメント木の上を降りながら境目を求める「セグメント木上の二分探索」については、セグメント木のリンク集も見てください。

  • 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜(けんちょん、Qiita)
    • 値を探す素朴な二分探索から始めて、std::lower_bound の意味、「条件を満たす最小の xx を求める」形への一般化、ok と ng の 2 変数で大小の向きを気にせずに書くめぐる式、の順に説明しています。最後の例は年齢当てゲームです。コードは C++ です。
    • 最終形のコードは真ん中を (ok + ng) / 2 で計算しています。範囲が 101810^{18} 程度になる問題では、ok + (ng - ok) / 2 に直して使ってください。
    • 年齢当てゲームのコードのコメント「mid 歳以上 right 歳以下」は、本文の流儀(半開区間 [left,right)[\mathit{left}, \mathit{right}))では「right 歳未満」の誤りです。
  • 競プロ典型 90 問 001 - Yokan Party の解説(E869120、GitHub)
    • 「答えで二分探索」の入門です。「スコアを MM 以上にできるか」という判定問題に言い換え、それを貪欲法で O(N)O(N) で解いて、MM を二分探索します。「最小値の最大化」は答えで二分探索になることが多い、という指摘と類題もあります。解説は画像 1 枚で、C++ のサンプルコードは同じリポジトリの sol/001.cpp にあります。
  • 二分探索をはじめからていねいに(北海道大学 HCPC、PDF)
    • 2016 年の勉強会のスライドです。配列上の二分探索と lower_bound・upper_bound から始めて、実数の二分探索(回数を固定してループ)、最小値の最大化、最大値の最小化、平均値の最大化を、例題を 1 問ずつ解きながら説明しています。どれも蟻本の例題で、ジャッジは POJ です。コードは C++ で、画像なのでコピーはできません。
  • AtCoder ABC 034 D - 食塩水(けんちょんの競プロ精進記録)
    • 「濃度を xx % 以上にできるか」という判定問題に言い換え、式を変形して「(食塩の量) − (食塩水の量) × xx / 100 の大きいほうから KK 個の和が 00 以上か」で判定しています。実数の二分探索を 50 回のループで行う C++ のコードつきです。
  • 二分探索(Binary Search)のアルゴリズム(アルゴリズムロジック)
    • 値を探す二分探索、lower_bound、条件を満たす最小の位置を求める一般化、平均値の最大化(ABC034 D)を 1 ページで説明しています。Python と C++ のコードと、練習問題の一覧つきです。
    • 中級編の自作の my_lower_bound には誤りがあります。r を arr.size() - 1 から始めているので、xx がすべての要素より大きいときに arr.size() を返せません。また、x == arr[mid] で途中で返しているので、同じ値が複数あると左端を返しません。説明の「lower_bound 関数と upper_bound 関数」も、upper_bound は「xx より大きい値を持つ左端」なので正しくありません。
    • 食塩水のコードは while (ng - ok > 1e-10) で打ち切っています。この問題では止まりますが、値が大きい問題では止まらなくなることがあります(下の「実数の二分探索」を見てください)。
  • 実数の二分探索・三分探索はループ回数を決め打ちしようね(えびちゃんの日記)
    • while (hi - lo > eps) のように幅で打ち切ると、浮動小数点数で表せる値が飛び飛びなせいで止まらなくなる例を示し、ループの回数を決め打ちするよう勧めています。必要な回数の見積もり方(初めの幅を 101810^{18}、許される誤差を 10−910^{-9} とすると 90 回で足りる)と、三分探索の場合の回数も載っています。コードは C++ です。
  • 浮動小数点型で素朴に二分探索をして大丈夫?(えびちゃんの日記)
    • 上の記事の続きにあたる発展的な内容です。止まるかどうかだけでなく、判定関数の丸め誤差のせいで答えがずれる例を挙げて、結果が正しいかを議論しています。コードは Rust です。
  • Re: 浮動小数点数の二分探索(えびちゃんの日記)
    • double のビット列を大小関係を保つ 64 bit 整数に変換し、整数の二分探索として 64 回程度で済ませる方法です。例題は ABC026 D で、コードは Rust です。
    • 「C++ は bit_cast を C++20 まで待つ必要がある」とあるのは執筆当時の話で、今は C++20 で使えます。
  • 二分探索 二分法 違い(うさぎ小屋)
    • 「二分探索」と「二分法」という言葉の違いを整理した短い記事です。競プロで「にぶたん」と呼ぶものがどちらにあたるかも書いています。

複数の質問について、それぞれ「何番目の操作の時点で条件を満たすようになるか」を二分探索したいとき、全部の質問の二分探索を 1 段ずつまとめて進め、操作の列を各段で 1 回ずつ頭からたどる手法です。

  • CODE THANKS FESTIVAL 2017 H - Union Sets(並列二分探索解法)(ARMERIA)
    • 並列二分探索が使える問題の形、図を使った処理の流れ、各段で質問を mid ごとに振り分けて Union-Find の操作を頭からやり直す C++ の実装を説明しています。計算量の見積もりと、部分永続 Union-Find による別解の紹介もあります。
  • 並列二分探索(パラレルバイナリサーチ)(迷いませんか?)
    • SPOJ の Meteors と上の Union Sets を C++ で解いています。説明は短めで、著者自身が計算量の見積もりに自信がないと書いているので、上の記事の補助として読んでください。
  • Segtree(AtCoder Library のドキュメント)
    • max_right と min_left の仕様が載っています。返り値は「区間に ff を適用した結果が true から false に変わる境目」として定義されていて、ff が単調なら「true になる最大の rr」と読めます。計算量は O(log⁡N)O(\log N) です。仕様の説明だけで、セグメント木を降りる仕組みは書かれていません。
  • セグメント木上の二分探索のカテゴリ(けんちょんの競プロ精進記録)
    • セグメント木上の二分探索を使う問題の解説が並んでいて、問題集として使えます。
  • bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
    • bisect_left・bisect_right・insort_left・insort_right の仕様と、ソート済みリストから「xx 未満の最大の要素」などを探すレシピがあります。key 引数は Python 3.10 で追加されたもので、それより古い環境では使えません。
    • 日本語訳が一部だけで、英語のまま残っている段落があります。レシピの find_ge のコメント「左端の項目がx以上であることを確認する」は、原文では「xx 以上の左端の項目を見つける」という意味です。
  • めぐる式二分探索 コピペで使えるPython実装(学習する天然ニューラルネット)
    • 判定関数 is_ok と ok・ng を渡すめぐる式二分探索の Python のテンプレートと、ABC146 C などでの使用例です。仕組みの説明は、けんちょんさんの記事などに任せています。
    • 「配列にできない関数を探索できる(bisect モジュールでは不可)」とありますが、Python 3.10 以降なら bisect_left(range(lo, hi), True, key=is_ok) のように、bisect でも判定関数のまま探せます。
  • std::lower_bound・std::upper_bound・std::partition_point(cpprefjp)
    • lower_bound は「指定した値以上の最初の位置」、upper_bound は「指定した値より大きい最初の位置」を返します。範囲がソートされていなくても、条件で区分化されていればよいこと、どちらも partition_point と同じ働きであることが書かれています。partition_point は判定関数を渡して境目を求める関数で、二分探索を一般化した形にあたります。
    • std::set や std::multiset に std::lower_bound を使うと、比較の回数は O(log⁡N)O(\log N) でもイテレータを進めるのに O(N)O(N) かかります。メンバ関数の s.lower_bound(x) を使ってください(cpprefjp の lower_bound のページにも、メンバ関数を使うようにと書いてあります)。

二分探索そのものを扱う講座はありませんが、二分探索を使う講座がいくつかあります。

  • Alien Trick
    • 「ちょうど kk 個選ぶ」という制約を、1 個ごとのペナルティ λ\lambda に置き換えて外し、λ\lambda を二分探索する手法の講座です。最適な個数が λ\lambda について単調になることを示し、二分探索の終了時に成り立つ条件まで丁寧に説明しています。難易度の高い講座です。
  • 永続セグメント木
    • 区間の kk 番目の値を求める問題で、ふつうに二分探索すると O(log⁡2N)O(\log^2 N) のところを、複数の木を同時に降りるセグメント木上の二分探索で O(log⁡N)O(\log N) にする方法を説明しています。
  • Wavelet Matrix(発展)
    • 「5. 総和に関する二分探索」の節で、単調な総和の条件を満たす境目を Wavelet Matrix の上で求めています。
  • 二分探索(日本語版 Wikipedia)、Binary search(英語版 Wikipedia)
    • 日本語版は英語版の訳です。重複がある場合に左端・右端を探す手続き(lower_bound・upper_bound にあたる)、順位や直前・直後の要素の求め方、指数探索などの変種が載っています。「実装上の問題」の節には、有名な本や Java の標準ライブラリで、真ん中の計算のオーバーフローのバグが長年見逃されていた話があります。答えで二分探索や実数の二分探索の話はありません。
    • 各言語のライブラリの節は、日本語版・英語版ともに古い情報を元にしています。
  • Binary search(cp-algorithms、英語)
    • 配列上の探索、lower_bound・upper_bound、単調な述語での探索とその正当性、答えで二分探索(平均値の最大化)、実数の探索(中間値の定理を使うので単調でなくてよい)、2 のべき乗の幅で進む方法、並列二分探索までを 1 ページで扱っています。オーバーフローの注意と C++20 の std::midpoint にも触れています。コードは C++ で、練習問題の一覧もあります。
    • 並列二分探索の節は、例の表と直後のコードで区間の取り方が違うので、読むときは混乱しないように気をつけてください。
  • Binary Search(USACO Guide、英語)
    • 単調な関数での二分探索の入門で、「true になる最後の位置」と「true になる最初の位置」の 2 つの書き方、よくある間違い(off-by-one、負の範囲、オーバーフロー)、練習問題の一覧があります。コードは C++・Java・Python から選べます。配列上の二分探索は、前提の別ページ Binary Search on a Sorted Array にあります。
    • 「Mistake 1」の Python のコードは hi = 0 になっていて(C++ と Java では hi = x)、説明している無限ループが起きません。「Mistake 2」の「負の奇数を 2 で割ると切り上がる」という説明は C++ と Java の話で、Python の // は切り捨てなので当てはまりません。
  • Binary Search(lovro、Topcoder、英語)
    • 述語が「no … no yes … yes」と並ぶときに二分探索できる、という形で一般化を説明した古典的なチュートリアルです。最後の no を探すときに真ん中を切り上げないと無限ループになる例や、実数の二分探索の打ち切り方(回数を固定する方法と、相対誤差で止める方法)もあります。
    • サイトの移行で表示が崩れていて、擬似コードのインデントが壊れていたり、例の数列が連結して表示されたりしています。練習問題のリンクは切れています。「Arrays.binary_search」は Java の Arrays.binarySearch の誤りです。
  • ABC146 C - Buy an Integer:値段は NN について単調増加なので、買える最大の NN を二分探索します。
  • 競技プログラミングの鉄則 A12 - Printer:tt 秒後までに印刷される枚数は tt について単調なので、KK 枚以上になる最小の tt を求めます。
  • 競プロ典型 90 問 001 - Yokan Party(★4):最小値の最大化です。上の解説を見てください。
  • ABC063 D - Widespread:爆発の回数を決め打ちして、すべての魔物を消せるかを判定します。
  • ABC023 D - 射撃王:得点を決め打ちすると風船ごとに割る期限が決まるので、期限の早い順に割れるかを判定します。
  • ABC174 E - Logs:最大値の最小化です。最も長い丸太を xx 以下にするのに必要な切断回数を数えます。
  • ABC144 E - Gluttony:成績を決め打ちし、組み合わせ方を貪欲に決めて、必要な修行の回数が KK 以下かを判定します。
  • ARC050 B - 花束:作る花束の個数を決め打ちして、作れるかを判定します。値が 101810^{18} まであるので、オーバーフローに注意が必要です。
  • ABC149 E - Handshake:幸福度の上がり方が xx 以上の握手が MM 通り以上あるような最大の xx を二分探索し、個数を数えるのにも二分探索を使います。
  • ABC034 D - 食塩水:平均値の最大化の典型です。上のけんちょんさんの記事が解説です。
  • ABC026 D - 高橋君ボール1号:f(t)f(t) は単調ではありませんが、f(0)<100f(0) < 100 で、tt が大きいと f(t)>100f(t) > 100 になるので、中間値の定理から f(t)=100f(t) = 100 となる tt を二分法で 1 つ見つけられます。
  • ABC269 E - Last Rook:行の範囲を半分に区切り、置かれているルークの数が行の数より少ないほうに空いた行がある、として 20 回以内の質問で探します。列も同じです。