✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-226

Binary Search on the Answer

Binary Search on the Answer is an optimization technique that uses binary search over a possible answer range instead of searching directly through an array.

Explanation

Overview

Binary Search on the Answer applies when a problem asks for the minimum or maximum value satisfying a condition, and that condition is monotonic. A monotonic condition changes in only one direction as the candidate answer increases or decreases, allowing half of the search space to be eliminated at each step.

Core idea

Instead of calculating the optimal answer directly, choose a candidate value and test whether it is feasible. If the candidate is feasible, search for a better answer in the appropriate direction. If it is infeasible, eliminate that portion of the search space.

How it works

Determine the minimum and maximum possible answers.; Define a feasibility function that checks a candidate answer.; Verify that the feasibility result is monotonic.; Calculate the midpoint of the current answer range.; If the midpoint is feasible, move toward a potentially better answer.; If it is not feasible, discard the invalid half.

Key concepts

Monotonic feasibility; Candidate answer; Search boundaries; Minimum feasible value; Maximum feasible value; Optimization problems

Time complexity

operation: Binary search iterations; complexity: O(log R), where R is the size of the candidate range; operation: Total algorithm; complexity: O(T × log R), where T is the time required by one feasibility check

Space complexity

Depends on the feasibility-check implementation; the binary-search control logic generally uses O(1) auxiliary space.

Example

problem: Find the minimum capacity required for a container to ship packages within a specified number of days.; packageWeights: 3; 2; maximumDays: 3; candidate: 6; feasibility: A capacity of 6 can ship the packages in three days: [3, 2], [2, 4], [1, 4].; result: The candidate capacity is feasible, so the search can test smaller capacities.

Example or application

Problem

Find the minimum capacity required for a container to ship packages within a specified number of days.

Package Weights

  • 3

  • 2

  • 2

  • 4

  • 1

  • 4

Maximum Days

3

Candidate

6

Feasibility

A capacity of 6 can ship the packages in three days: [3, 2], [2, 4], [1, 4].

Result

The candidate capacity is feasible, so the search can test smaller capacities.

Definition

Binary Search on the Answer applies when a problem asks for the minimum or maximum value satisfying a condition, and that condition is monotonic. A monotonic condition changes in only one direction as the candidate answer increases or decreases, allowing half of the search space to be eliminated at each step.

Core Idea

Instead of calculating the optimal answer directly, choose a candidate value and test whether it is feasible. If the candidate is feasible, search for a better answer in the appropriate direction. If it is infeasible, eliminate that portion of the search space.

Monotonicity

Description

A feasibility condition must have a consistent transition between false and true, or true and false, across the candidate range.

Minimum Example

Condition

Can the work be completed within x days?

Pattern

false, false, false, true, true, true

Goal

Find the smallest feasible x.

Maximum Example

Condition

Can the selected minimum distance be at least x?

Pattern

true, true, true, false, false, false

Goal

Find the largest feasible x.

How It Works

  • Determine the minimum and maximum possible answers.

  • Define a feasibility function that checks a candidate answer.

  • Verify that the feasibility result is monotonic.

  • Calculate the midpoint of the current answer range.

  • If the midpoint is feasible, move toward a potentially better answer.

  • If it is not feasible, discard the invalid half.

  • Continue until the optimal boundary is identified.

Feasibility Function

Description

The feasibility function determines whether a proposed answer satisfies all problem constraints.

Pseudocode

  • function feasible(candidate):

  • simulate the problem using candidate

  • return whether all constraints are satisfied

Implementation

Language

Pseudocode

Code

  • function minimumFeasible(low, high):

  • while low < high:

  • mid = low + (high - low) // 2

  • if feasible(mid):

  • high = mid

  • else:

  • low = mid + 1

  • return low

Time Complexity

OperationComplexity

Binary search iterations

O(log R), where R is the size of the candidate range

Total algorithm

O(T × log R), where T is the time required by one feasibility check

Space Complexity

Depends on the feasibility-check implementation; the binary-search control logic generally uses O(1) auxiliary space.

Key Concepts

  • Monotonic feasibility

  • Candidate answer

  • Search boundaries

  • Minimum feasible value

  • Maximum feasible value

  • Optimization problems

  • Feasibility checking

Advantages

  • Can transform difficult optimization problems into efficient decision problems.

  • Reduces large numerical search spaces logarithmically.

  • Works with many scheduling, allocation, and partitioning problems.

  • Separates feasibility checking from answer optimization.

Limitations

  • The candidate condition must be monotonic.

  • Designing a correct feasibility function can be difficult.

  • Incorrect lower or upper bounds can exclude the true answer.

  • The total performance depends on the cost of each feasibility check.

Applications

  • Minimum shipping capacity

  • Book allocation problems

  • Workload distribution

  • Maximum minimum distance problems

  • Scheduling optimization

  • Resource allocation

  • Finding minimum required processing capacity

Related Topics

  • Binary Search

  • Greedy Algorithms

  • Optimization

  • Monotonic Functions

  • Feasibility Problems

Practice Questions

QuestionAnswer

What is Binary Search on the Answer?

A technique that searches a candidate answer range using a monotonic feasibility condition.

What property must the feasibility condition have?

It must be monotonic across the candidate answer range.

What is the complexity when the candidate range contains R possible values and each feasibility check costs T?

O(T × log R).

Why is it useful for optimization problems?

It can identify the smallest or largest feasible answer without checking every candidate.

Learning Objectives

  • Explain the central idea and purpose of binary search on the answer.

  • Identify the assumptions, inputs, and conditions relevant to binary search on the answer.

  • Evaluate an application of binary search on the answer for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures