Mastering Binary Search with Codeforces Problems (Rating Wise)

Binary Search is one of the most fundamental and powerful techniques in competitive programming. Many beginners only use it to find an element in a sorted array, but in contests, Binary Search is used in much more creative ways.

This post lists problems ordered by rating (800 → 2000) so you can practice progressively.

Easy (800 – 1200)

706B — Interesting Drink — Simple use of binary search with arrays.

1352C — K-th Not Divisible by n — Binary search on the answer.

812C — Sagheer and Nubian Market — Binary search to maximize affordable items.

Medium (1300 – 1600)

371C — Hamburgers — Binary search on the maximum number of burgers.

1181B — Split a Number — Binary search + string handling.

1486C2 — Guessing the Greatest (Hard version) — Interactive + binary-search reasoning.

Hard (1700 – 2000+)

1304C — Air Conditioner — Simulation with binary search bounds.

1157C2 — Increasing Subsequence (Hard) — Greedy + binary search ideas.

148E — Porcelain — Advanced DP + binary-search uses.

1370C — Number Game — Binary search + math reasoning.

Tips to Master Binary Search

1. Always reframe into a "yes/no" question you can test in O(n) or better.

2. Practice searching on the answer space (min time, max items, minimal radius, etc.).

3. Learn lower_bound / upper_bound behaviour and watch out for off-by-one errors.

4. Binary Search appears everywhere — arrays, functions, probabilities, and geometry. Look for monotonicity!

C++ Binary Search Templates

1) Classic lower_bound / upper_bound style

// find first index i in [l, r) such that check(i) is true
int binary_search_first_true(int l, int r) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l; // maybe r; verify check(l) before using
}

2) Binary search on answer (example: maximum x satisfying condition)

long long lo = 0, hi = 1e18; // set hi to an upper bound
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (good(mid)) { // good(mid) => mid is feasible
        lo = mid + 1; // try larger
    } else {
        hi = mid - 1; // reduce
    }
}
// hi will hold the maximum feasible value

Happy coding and good luck with your binary search journey!

Feel free to share your solutions and ask questions in the comments below.