Overview
Binary search on answer converts an optimization problem into repeated yes/no feasibility checks. If feasibility is monotone over the candidate answer range, binary search can find the boundary value.
CoreSource checked
Binary Search on Answer
Finds an optimal numeric answer by binary searching a monotone feasibility predicate.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Parametric Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Parametric Binary Search
Core Concepts
candidate searchobjective functionsorted search spaceparametric searchcandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log r)
Average
O(T log r)
Worst
O(T log r)
Space
O(1)
When to Use
- Use when the predicate changes from false to true, or true to false, only once.
- Use when bounds and precision requirements are known.
When Not to Use
- Avoid when feasibility is not monotone over the search range.
- Avoid when computing the predicate is too expensive for repeated calls.
What It Does
- Defines a monotone feasibility predicate
- Searches the numeric answer range
- Keeps the side that can still contain the boundary answer
Use Cases
- Minimum feasible capacity or maximum feasible threshold problems
- Scheduling and allocation problems with monotone checks
- Integer or real-valued optimization with clear bounds
Inputs
- Numeric answer range
- Monotonic feasibility test
Outputs
- Best feasible answer
Key Formulas (1)
Feasibility split
if feasible(mid), high = mid else low = mid + 1
if feasible(mid), high = mid else low = mid + 1Uses a monotonic yes/no test to keep the half that can still contain the best answer.
Pseudocode
- 1.Choose low and high bounds for the answer
- 2.While the search interval is not finished
- 3.Set mid to the candidate answer
- 4.Run the monotone feasibility check
- 5.Move the feasible or infeasible bound according to the invariant
- 6.Return the boundary answer
Canonical Example
- Input
- ship packages [3, 2, 2] in 2 days; test capacity
- Output
- minimum capacity = 4
- Explanation
- Capacity 3 is infeasible, capacity 4 is feasible, and feasibility stays true for larger capacities.
Implementation Notes
- Write tests proving the predicate is monotone on small examples.
- Keep invariant comments for which bound is feasible or infeasible.
- Separate integer and floating-point termination logic.
Common Pitfalls
- The predicate direction must match how bounds are updated.
- Integer midpoint and termination rules can loop forever.
- Real-valued searches need an explicit tolerance or iteration limit.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow a feasible boundary moving through a numeric answer range.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 6: Choose low and high bounds for the answer
answer-range-searchNotes
The algorithm is only as valid as the monotonicity of the feasibility predicate.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookAlgorithms textbook support for Binary Search on Answer invariants, search ordering, correctness argument, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageVariant ofBinary Search
Binary search on answer applies binary search to a monotone predicate over answer values.
Conceptual neighborBinary Search in Answer Space
Both solve optimization-style problems through monotone decision checks.
Related Algorithms
Tags
SearchOptimizationSorted Data