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:
- Define the search space: reasonable minimum and maximum answer values
- Pick a middle candidate answer
- Test: "Is this candidate feasible?" (Can I complete the task in this time?)
- If yes, the answer might be smaller → search the lower half
- 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.