🧭 本記事は Codeforcesの勉強方法：アルゴリズム難易度分布に基づく効率的な問題解き戦略 のシリーズの一部です。
本シリーズでは、アルゴリズムごとに Codeforces の代表的な問題を整理し、典型的な Binary Search パターンや考え方を紹介しています。
💡 Binary Search（二分探索）とは
Binary Search は、整列済み配列や範囲に対して高速に探索する手法 です。
単純な探索では O(N) のところを O(log N) で答えを求められるのが強みです。
🎯 学習の狙い
- 標準的な二分探索を理解し、境界条件を正確に扱えるようにする
- 配列だけでなく、関数や解の範囲に対しても二分探索を応用する
- Binary Search と Greedy / DP を組み合わせる典型パターンを学ぶ
📘 推奨難易度：1300〜1800
B〜C問題中心で、基礎から応用まで幅広く練習できる範囲です。
🧩 例題リスト
| 問題 | 難易度 | タグ | 解法概要 | 備考 |
|---|---|---|---|---|
| D. Pair of Topics | 1400 | binary search | 二つの配列を合併する必要ある | 基本二分探索練習 |
| C. Hamburgers | 1600 | binary search | 二分探索で答えを仮定してチェックする | |
| B. Password | 1700 | binary search, dp,kmo | 二分探索で長さを仮定してチェックする | kmp |
| F. Final Boss | 1500 | binary search | 普通の二分探索 | |
| C. Keshi Is Throwing a Party | 1500 | binary search, grredy | 欲張り法 + 二分探索 | |
| D. Kefa and Company | 1600 | binary search, sorting | ソート＋範囲条件二分探索 | 中級者向け挑戦 |
| C. Vasya and String | 1500 | binary search, sorting | 二分探索+累積和 |
🧠 Binary Search 実装時のチェックポイント
-
境界条件を明確に
- 左右端の扱いで WA が多発する
-
whileループ or 再帰の違いを理解
- mid の計算方法や更新タイミングに注意
-
配列だけでなく「関数の条件」への応用
- 汎用的な解法パターンを覚える
-
Greedy や DP と組み合わせる場合
- 答えの範囲を二分探索、条件判定を Greedy/DP で計算
🧾 メモ・考察ログ
- 単純探索を二分に置き換えるだけで大幅に高速化可能
- 配列以外の問題（最大値/最小値、最小操作回数など）でも応用できる
- 上級では「探索範囲をうまく設定する」ことがキモ
🔗 関連記事
- 【Codeforces】Sorting アルゴリズム問題集
- 【Codeforces】Greedy アルゴリズム問題集
- Codeforcesの勉強方法：アルゴリズム難易度分布に基づく効率的な問題解き戦略
🧩 更新履歴
| 日付 | 内容 |
|---|---|
| 2025-10-28 | 初版公開 |
💬 コメント・改善提案は随時歓迎です！
次のテーマ候補：Graphs,Data Structures,Trees