Skip to content

Foundations -> Binary Search

Search on sorted data and on monotone answers: learn the invariant-first template before memorizing implementations.

  • Topic slug: foundations/binary-search
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 0
  • Curated external problems: 6

Microtopics

  • lower_bound
  • upper_bound
  • first-true
  • last-true
  • answer-search
  • overflow
  • continuous-bsearch

Learning Sources

Source Type
cp-algorithms binary search Reference
USACO Guide binary search Reference
Codeforces EDU binary search Course

Practice Sources

Source Type
Codeforces binary-search tag Practice
CSES Problem Set Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
032 - Binary Search AtCoder Easy - - - Membership; Sorted-Array Official warmup for binary search on sorted data.
C - Buy an Integer AtCoder Medium - - - Digit-Length; Math Search over a monotone price function.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Array Division CSES Medium - Proof-Heavy; Greedy-Heavy Binary Search; Greedy Feasibility Checks; Arrays Binary-Search-On-Answer; Partitioning; Greedy-Check; Partition A standard partitioning benchmark that teaches how to build a monotone check.
Factory Machines CSES Medium - Proof-Heavy; Math-Heavy Binary Search; Monotone Predicates; Prefix Counting Binary-Search-On-Answer; Monotonicity; Counting; Monotone-Predicate; Minimize-Answer A canonical binary-search-on-answer problem with a clean monotone feasibility check.
Magic Powder - 2 Codeforces Medium - Proof-Heavy; Greedy-Heavy Binary Search; Greedy Checks; Resource Counting Binary-Search-On-Answer; Resource-Feasibility A popular feasibility-search problem with a very reusable binary-search pattern.
Maximum Median Codeforces Medium - Proof-Heavy; Math-Heavy Binary Search; Median Reasoning; Greedy Binary-Search-On-Answer; Median A classic binary-search benchmark where the objective is to maximize a median value.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
FACTORYMACHINES Factory Machines primary medium answer binary search; monotone feasibility; production rate accumulation Note Code

Regeneration

python3 scripts/generate_problem_catalog.py