Manoj_mk's blog

By Manoj_mk, history, 16 months ago, In English

When to Use Binary Search in Competitive Programming

Binary Search is one of the most powerful tools in a competitive programmer’s toolkit. While it’s classically taught for searching in sorted arrays, its real power lies in solving a wide variety of problems efficiently by reducing the search space.

In this blog, we’ll cover when and how to use binary search, along with problem types where it's especially useful.


Prerequisite

You must know the basic binary search algorithm:

int low = 0, high = n-1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (condition) low = mid + 1;
    else high = mid - 1;
}

When to Use Binary Search

Binary search is applicable when:

1. The Answer Lies in a Monotonic Search Space

If you can frame the problem such that the answer lies in a monotonic function (increasing or decreasing), then binary search can be used to "search the answer".

Examples:

  • Minimum possible value x such that a condition is satisfied
  • Maximum number of items satisfying some budget or constraint

2. Finding First/Last Occurrence in a Sorted Array

This is the classic usage.

  • Find the first element >= target (lower bound)
  • Find the last element <= target (upper bound)

3. On the Answer

If the final answer lies in a range and you can write a check(mid) function that answers whether a given mid is valid or not, then binary search can be used directly on the answer.

Template:

int low = L, high = R, ans = -1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (check(mid)) {
        ans = mid;
        high = mid - 1; // or low = mid + 1 depending on min/max
    } else {
        low = mid + 1;
    }
}

4. Binary Search on Real Numbers (Floating Point Search)

Used when the answer lies in a real number range. For example:

  • Minimum time to complete a task
  • Geometry problems (minimum distance, radius, etc.)
double low = 0.0, high = 1e9;
for (int i = 0; i < 100; ++i) { // or while (high - low > EPS)
    double mid = (low + high) / 2;
    if (check(mid)) high = mid;
    else low = mid;
}

5. Binary Search on the Answer with DP/Greedy

Some problems can be solved by binary searching on the answer and verifying feasibility using greedy or dynamic programming.

Examples:

  • Minimize maximum subarray sum (Greedy)
  • Aggressive Cows (check with greedy)
  • Allocate books problem
  • Longest segment with some property (use prefix sums + BS)

6. Implicit Binary Search

Sometimes the array is not given, but the logic to compute check(mid) exists.

For example:

  • Searching in a function space
  • Searching in virtual array: like sorted prefix sum, suffix sum, etc.

Common Problem Patterns

Problem Type Binary Search Use Case
Array searching (sorted) Find position / first/last occurrence
Maximize/Minimize with constraints Binary search on the answer
Budget-based problems Max items within budget (greedy + BS)
Partitioning problems Minimize largest sum (prefix + greedy)
Floating point answers Geometry, probability, timing
Time-based simulations Minimum time to do a task (greedy + BS)

Tips

  • Always ask: "Can I reframe this problem into a YES/NO question with a monotonic answer?"
  • Think about edge cases (mid, low, high updates).
  • Watch out for overflows: use mid = low + (high - low) / 2
  • Prefer while (low < high) when possible

Practice Problems

  1. Aggressive cows — SPOJ
  2. EKO — SPOJ
  3. Minimum Number of Days to Make m Bouquets — Leetcode
  4. Find First and Last Position of Element — Leetcode
  5. Shipping Packages in D Days — Leetcode

Conclusion

Whenever you need to optimize a quantity, check feasibility, or search within a range, think Binary Search. It can reduce your solution from O(n) to O(log n), making the difference between TLE and AC!

  • Vote: I like it
  • +9
  • Vote: I do not like it