Course contentsShow
← Computer Science
Lesson 815 of 2,87219. Searching and SelectionFree lesson

Binary Search on Answer Space

Apply binary search to find optimal solutions by searching over possible answer values instead of array indices.

Binary Search on Answer Space

What You'll Learn

You'll learn how to use binary search not to find an element in an array, but to efficiently search for the optimal answer to a problem by testing possible solution values.

The Core Idea

Traditional binary search finds an element in a sorted array. But what if instead of searching through an array, you search for the answer itself?

Binary Search on Answer Space means applying binary search to find an optimal value (minimum or maximum) by treating all possible answers as a sorted range and testing whether each candidate answer is feasible.

How It Works

Imagine you need to find "the minimum time needed to complete a task." Instead of checking every possible time value (1 minute, 2 minutes, 3 minutes...), you:

  1. Define the search space: reasonable minimum and maximum answer values
  2. Pick a middle candidate answer
  3. Test: "Is this candidate feasible?" (Can I complete the task in this time?)
  4. If yes, the answer might be smaller → search the lower half
  5. If no, the answer must be larger → search the upper half

Real-World Analogy

Think of guessing how many slices of pizza your friend can eat. Instead of watching them eat one slice at a time, you ask: "Can you eat 10 slices?" If they say no, you know the answer is less than 10. You then ask "Can you eat 5 slices?" and narrow down from there. You're searching the space of possible answers (1 to 20 slices), not searching through a list.

The Key Requirement

The answer space must have a monotonic property: if a value x works, then all values greater (or smaller, depending on the problem) must also work. This sorted property lets binary search apply.

Key Takeaway: Binary search isn't just for finding elements in arrays—you can search for optimal answers by testing candidate values in a sorted solution space, reducing O(n) checking to O(log n) iterations.