二分探索のリンク集
二分探索について、参考になる記事や資料をまとめました。
二分探索は、答えの候補が並んでいて、ある境目より手前では条件を満たさず、そこから先ではずっと満たす(単調性がある)ときに、その境目を 回の判定で求める手法です。ソート済みの配列から値を探すのが基本の形で、C++ の std::lower_bound や Python の bisect がこれにあたります。
競プロでよく使うのは、その一般化です。「答えを 以下にできるか」のような判定問題が について単調なら、答えそのものを二分探索で求められます(答えで二分探索)。最小値の最大化・最大値の最小化や、平均値の最大化がこの形の典型です。実数の範囲でも同じように探せますが、打ち切り方に注意が必要です。
実装では、条件を満たす側の端を ok、満たさない側の端を ng として、ok と ng が隣り合うまで真ん中で区切る書き方(めぐる式二分探索)がよく使われます。範囲が大きいときは、真ん中を (ok + ng) / 2 で計算すると和が型の範囲を超えることがあるので、ok + (ng - ok) / 2 のように書くと安全です。
セグメント木の上を降りながら境目を求める「セグメント木上の二分探索」については、セグメント木のリンク集も見てください。
まず読むもの
Section titled “まず読むもの”- 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜(けんちょん、Qiita)
- 値を探す素朴な二分探索から始めて、
std::lower_boundの意味、「条件を満たす最小の を求める」形への一般化、okとngの 2 変数で大小の向きを気にせずに書くめぐる式、の順に説明しています。最後の例は年齢当てゲームです。コードは C++ です。 - 最終形のコードは真ん中を
(ok + ng) / 2で計算しています。範囲が 程度になる問題では、ok + (ng - ok) / 2に直して使ってください。 - 年齢当てゲームのコードのコメント「mid 歳以上 right 歳以下」は、本文の流儀(半開区間 )では「right 歳未満」の誤りです。
- 値を探す素朴な二分探索から始めて、
- 競プロ典型 90 問 001 - Yokan Party の解説(E869120、GitHub)
- 「答えで二分探索」の入門です。「スコアを 以上にできるか」という判定問題に言い換え、それを貪欲法で で解いて、 を二分探索します。「最小値の最大化」は答えで二分探索になることが多い、という指摘と類題もあります。解説は画像 1 枚で、C++ のサンプルコードは同じリポジトリの
sol/001.cppにあります。
- 「答えで二分探索」の入門です。「スコアを 以上にできるか」という判定問題に言い換え、それを貪欲法で で解いて、 を二分探索します。「最小値の最大化」は答えで二分探索になることが多い、という指摘と類題もあります。解説は画像 1 枚で、C++ のサンプルコードは同じリポジトリの
- 二分探索をはじめからていねいに(北海道大学 HCPC、PDF)
- 2016 年の勉強会のスライドです。配列上の二分探索と
lower_bound・upper_boundから始めて、実数の二分探索(回数を固定してループ)、最小値の最大化、最大値の最小化、平均値の最大化を、例題を 1 問ずつ解きながら説明しています。どれも蟻本の例題で、ジャッジは POJ です。コードは C++ で、画像なのでコピーはできません。
- 2016 年の勉強会のスライドです。配列上の二分探索と
平均値の最大化
Section titled “平均値の最大化”- AtCoder ABC 034 D - 食塩水(けんちょんの競プロ精進記録)
- 「濃度を % 以上にできるか」という判定問題に言い換え、式を変形して「(食塩の量) − (食塩水の量) × / 100 の大きいほうから 個の和が 以上か」で判定しています。実数の二分探索を 50 回のループで行う C++ のコードつきです。
- 二分探索(Binary Search)のアルゴリズム(アルゴリズムロジック)
- 値を探す二分探索、
lower_bound、条件を満たす最小の位置を求める一般化、平均値の最大化(ABC034 D)を 1 ページで説明しています。Python と C++ のコードと、練習問題の一覧つきです。 - 中級編の自作の
my_lower_boundには誤りがあります。rをarr.size() - 1から始めているので、 がすべての要素より大きいときにarr.size()を返せません。また、x == arr[mid]で途中で返しているので、同じ値が複数あると左端を返しません。説明の「lower_bound 関数と upper_bound 関数」も、upper_boundは「 より大きい値を持つ左端」なので正しくありません。 - 食塩水のコードは
while (ng - ok > 1e-10)で打ち切っています。この問題では止まりますが、値が大きい問題では止まらなくなることがあります(下の「実数の二分探索」を見てください)。
- 値を探す二分探索、
実数の二分探索
Section titled “実数の二分探索”- 実数の二分探索・三分探索はループ回数を決め打ちしようね(えびちゃんの日記)
while (hi - lo > eps)のように幅で打ち切ると、浮動小数点数で表せる値が飛び飛びなせいで止まらなくなる例を示し、ループの回数を決め打ちするよう勧めています。必要な回数の見積もり方(初めの幅を 、許される誤差を とすると 90 回で足りる)と、三分探索の場合の回数も載っています。コードは C++ です。
- 浮動小数点型で素朴に二分探索をして大丈夫?(えびちゃんの日記)
- 上の記事の続きにあたる発展的な内容です。止まるかどうかだけでなく、判定関数の丸め誤差のせいで答えがずれる例を挙げて、結果が正しいかを議論しています。コードは Rust です。
- Re: 浮動小数点数の二分探索(えびちゃんの日記)
doubleのビット列を大小関係を保つ 64 bit 整数に変換し、整数の二分探索として 64 回程度で済ませる方法です。例題は ABC026 D で、コードは Rust です。- 「C++ は
bit_castを C++20 まで待つ必要がある」とあるのは執筆当時の話で、今は C++20 で使えます。
- 二分探索 二分法 違い(うさぎ小屋)
- 「二分探索」と「二分法」という言葉の違いを整理した短い記事です。競プロで「にぶたん」と呼ぶものがどちらにあたるかも書いています。
並列二分探索
Section titled “並列二分探索”複数の質問について、それぞれ「何番目の操作の時点で条件を満たすようになるか」を二分探索したいとき、全部の質問の二分探索を 1 段ずつまとめて進め、操作の列を各段で 1 回ずつ頭からたどる手法です。
- CODE THANKS FESTIVAL 2017 H - Union Sets(並列二分探索解法)(ARMERIA)
- 並列二分探索が使える問題の形、図を使った処理の流れ、各段で質問を
midごとに振り分けて Union-Find の操作を頭からやり直す C++ の実装を説明しています。計算量の見積もりと、部分永続 Union-Find による別解の紹介もあります。
- 並列二分探索が使える問題の形、図を使った処理の流れ、各段で質問を
- 並列二分探索(パラレルバイナリサーチ)(迷いませんか?)
- SPOJ の Meteors と上の Union Sets を C++ で解いています。説明は短めで、著者自身が計算量の見積もりに自信がないと書いているので、上の記事の補助として読んでください。
セグメント木上の二分探索
Section titled “セグメント木上の二分探索”- Segtree(AtCoder Library のドキュメント)
max_rightとmin_leftの仕様が載っています。返り値は「区間に を適用した結果が true から false に変わる境目」として定義されていて、 が単調なら「true になる最大の 」と読めます。計算量は です。仕様の説明だけで、セグメント木を降りる仕組みは書かれていません。
- セグメント木上の二分探索のカテゴリ(けんちょんの競プロ精進記録)
- セグメント木上の二分探索を使う問題の解説が並んでいて、問題集として使えます。
Python
Section titled “Python”- bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
bisect_left・bisect_right・insort_left・insort_rightの仕様と、ソート済みリストから「 未満の最大の要素」などを探すレシピがあります。key引数は Python 3.10 で追加されたもので、それより古い環境では使えません。- 日本語訳が一部だけで、英語のまま残っている段落があります。レシピの
find_geのコメント「左端の項目がx以上であることを確認する」は、原文では「 以上の左端の項目を見つける」という意味です。
- めぐる式二分探索 コピペで使える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を使うと、比較の回数は でもイテレータを進めるのに かかります。メンバ関数のs.lower_bound(x)を使ってください(cpprefjp のlower_boundのページにも、メンバ関数を使うようにと書いてあります)。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”二分探索そのものを扱う講座はありませんが、二分探索を使う講座がいくつかあります。
- Alien Trick
- 「ちょうど 個選ぶ」という制約を、1 個ごとのペナルティ に置き換えて外し、 を二分探索する手法の講座です。最適な個数が について単調になることを示し、二分探索の終了時に成り立つ条件まで丁寧に説明しています。難易度の高い講座です。
- 永続セグメント木
- 区間の 番目の値を求める問題で、ふつうに二分探索すると のところを、複数の木を同時に降りるセグメント木上の二分探索で にする方法を説明しています。
- Wavelet Matrix(発展)
- 「5. 総和に関する二分探索」の節で、単調な総和の条件を満たす境目を Wavelet Matrix の上で求めています。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- 二分探索(日本語版 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の誤りです。
ソート済みの配列から探す
Section titled “ソート済みの配列から探す”- 競技プログラミングの鉄則 A11 - Binary Search 1:ソート済みの配列から値の位置を探す、一番基本の形です。
- ABC077 C - Snuke Festival:中部のパーツを固定し、それより小さい上部と大きい下部の個数を
lower_bound・upper_boundで数えます。 - ABC143 D - Triangles:ソートして 2 本を固定し、3 本目になれる棒の本数を二分探索で数えます。
答えで二分探索
Section titled “答えで二分探索”- ABC146 C - Buy an Integer:値段は について単調増加なので、買える最大の を二分探索します。
- 競技プログラミングの鉄則 A12 - Printer: 秒後までに印刷される枚数は について単調なので、 枚以上になる最小の を求めます。
- 競プロ典型 90 問 001 - Yokan Party(★4):最小値の最大化です。上の解説を見てください。
- ABC063 D - Widespread:爆発の回数を決め打ちして、すべての魔物を消せるかを判定します。
- ABC023 D - 射撃王:得点を決め打ちすると風船ごとに割る期限が決まるので、期限の早い順に割れるかを判定します。
- ABC174 E - Logs:最大値の最小化です。最も長い丸太を 以下にするのに必要な切断回数を数えます。
- ABC144 E - Gluttony:成績を決め打ちし、組み合わせ方を貪欲に決めて、必要な修行の回数が 以下かを判定します。
- ARC050 B - 花束:作る花束の個数を決め打ちして、作れるかを判定します。値が まであるので、オーバーフローに注意が必要です。
- ABC149 E - Handshake:幸福度の上がり方が 以上の握手が 通り以上あるような最大の を二分探索し、個数を数えるのにも二分探索を使います。
平均値の最大化
Section titled “平均値の最大化”- ABC034 D - 食塩水:平均値の最大化の典型です。上のけんちょんさんの記事が解説です。
実数の二分探索
Section titled “実数の二分探索”- ABC026 D - 高橋君ボール1号: は単調ではありませんが、 で、 が大きいと になるので、中間値の定理から となる を二分法で 1 つ見つけられます。
インタラクティブ
Section titled “インタラクティブ”- ABC269 E - Last Rook:行の範囲を半分に区切り、置かれているルークの数が行の数より少ないほうに空いた行がある、として 20 回以内の質問で探します。列も同じです。
このブログの記事
Section titled “このブログの記事”ソート済みの配列から探す
Section titled “ソート済みの配列から探す”- 牛客小白月赛138 C - AND and OR
- 値でソートした列から、相手の値を二分探索で探しています。
- ABC480 D - Concatenation of Prefixes
- 増加列 について、 となる最大の を二分探索で求めています。
答えで二分探索
Section titled “答えで二分探索”- DOJ Beginner Contest 8 C - Mochi
- 「 組作れるか」を貪欲に判定し、作れる最大の を二分探索で求めています。
- DOJ Beginner Contest 11 F - Laboratory
- 日目に選べる最大の種類数が について単調であることを示し、 種類以上選べる最初の日を二分探索で求めています。
- ABC480 E - Product-Bounded Arithmetic Sequences
- 総積が公差 について単調増加なので、総積が 以下になる の個数を二分探索で求めています。
- 競プロキャンプ2026関西 A - km - n = k
- 割り算で直接求められる を、「 を満たす最大の 」として二分探索で求めています。
インタラクティブ
Section titled “インタラクティブ”- SamCoding Round 7 (Div. 2) H - Mysterious Valley
- 高さの列は単調ではありませんが、「左端では下り、右端では上り」という状態を保ったまま区間を半分にしていき、谷を見つけています。
- SamCoding Round 7 (Div. 2) J - Lying Guard
- 1 回だけ嘘をつく相手に、同じ質問を 3 回ずつして多数決をとりながら二分探索しています。
- ShareOJ - Truth or Lie
- 最初の質問で相手が嘘つきかどうかを調べてから、ふつうの二分探索をしています。
セグメント木上の二分探索
Section titled “セグメント木上の二分探索”- AALC001 C - Binary Search on a Segment Tree
- 和のセグメント木で
max_right・min_leftを使い、和が 未満のまま伸ばせる範囲を求めています。
- 和のセグメント木で
- AALC001 L - Swap between Arrays
- 区間の和と接頭辞の和の最大値をセグメント木に載せ、
max_rightで和が初めて正になる位置を求めています。
- 区間の和と接頭辞の和の最大値をセグメント木に載せ、