Binary Search on Answer Technique in DSA Java

Mental Model

We guess an answer and check if it works, then adjust our guess by cutting the search space in half each time.

Analogy: Like guessing the weight of a box by trying weights and narrowing down the range until you find the exact weight.

Range of answers: [low -------- mid -------- high]
                 ↑          ↑           ↑
                 low       mid         high
We check mid, then move low or high to narrow the range.

Dry Run Walkthrough

Input: Find minimum maximum pages per student to allocate 4 students for books with pages [10, 20, 30, 40]

Goal: Find the smallest maximum pages a student can read so all books are allocated to 4 students

Step 1: Set low to max pages (40), high to sum pages (100), mid = (40+100)/2=70

Range: [40 -------- 70 -------- 100]
Check mid=70

Why: We start with the smallest possible max (largest single book) and largest possible max (all books together)

Step 2: Check if allocation possible with max pages 70: allocate books to students without exceeding 70

Students allocation: [10,20,30] sum=60 ≤70 (student 1), [40] sum=40 ≤70 (student 2), total students used=2 ≤4

Why: Since 2 students suffice, 70 is a valid max, try smaller max to minimize

Step 3: Set high = mid - 1 = 69, mid = (40+69)/2=54

Range: [40 -------- 54 -------- 69]
Check mid=54

Why: Try smaller max to see if allocation still possible

Step 4: Check allocation with max pages 54: allocate books

Students allocation: [10,20] sum=30 ≤54 (student 1), [30] sum=30 ≤54 (student 2), [40] sum=40 ≤54 (student 3), total students=3 ≤4

Why: 3 students suffice, try smaller max

Step 5: Set high = mid - 1 = 53, mid = (40+53)/2=46

Range: [40 -------- 46 -------- 53]
Check mid=46

Why: Try smaller max again

Step 6: Check allocation with max pages 46

Students allocation: [10,20] sum=30 ≤46 (student 1), [30] sum=30 ≤46 (student 2), [40] sum=40 ≤46 (student 3), total students=3 ≤4

Why: 3 students suffice, try smaller max

Step 7: Set high = mid - 1 = 45, mid = (40+45)/2=42

Range: [40 -------- 42 -------- 45]
Check mid=42

Why: Try smaller max

Step 8: Check allocation with max pages 42

Students allocation: [10,20] sum=30 ≤42 (student 1), [30] sum=30 ≤42 (student 2), [40] sum=40 ≤42 (student 3), total students=3 ≤4

Why: 3 students suffice, try smaller max

Step 9: Set high = mid - 1 = 41, mid = (40+41)/2=40

Range: [40 -------- 40 -------- 41]
Check mid=40

Why: Try smallest max possible

Step 10: Check allocation with max pages 40

Students allocation: [10,20] sum=30 ≤40 (student 1), [30] sum=30 ≤40 (student 2), [40] sum=40 ≤40 (student 3), total students=3 ≤4

Why: 3 students suffice, try smaller max but low=40 so stop

Result:

Final answer: 40
Allocation possible with max pages 40 for 4 students

Annotated Code

DSA Java

public class BinarySearchOnAnswer {
    // Check if books can be allocated to students with maxPages limit
    static boolean canAllocate(int[] books, int students, int maxPages) {
        int requiredStudents = 1;
        int currentSum = 0;
        for (int pages : books) {
            if (pages > maxPages) return false; // single book exceeds maxPages
            if (currentSum + pages > maxPages) {
                requiredStudents++;
                currentSum = pages;
                if (requiredStudents > students) return false;
            } else {
                currentSum += pages;
            }
        }
        return true;
    }

    // Binary search on answer to find minimum max pages
    static int findMinMaxPages(int[] books, int students) {
        int low = 0;
        int high = 0;
        for (int pages : books) {
            low = Math.max(low, pages); // max single book
            high += pages; // sum all pages
        }
        int result = high;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canAllocate(books, students, mid)) {
                result = mid; // mid is valid, try smaller
                high = mid - 1;
            } else {
                low = mid + 1; // mid too small, increase
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] books = {10, 20, 30, 40};
        int students = 4;
        int answer = findMinMaxPages(books, students);
        System.out.println(answer);
    }
}

if (pages > maxPages) return false; // single book exceeds maxPages

guard against impossible allocation if a single book is larger than maxPages

if (currentSum + pages > maxPages) { requiredStudents++; currentSum = pages; if (requiredStudents > students) return false; }

start new student allocation when current sum exceeds maxPages, fail if too many students needed

low = Math.max(low, pages); high += pages;

initialize search range: low is largest single book, high is sum of all pages

if (canAllocate(books, students, mid)) { result = mid; high = mid - 1; } else { low = mid + 1; }

binary search step: if mid works, try smaller; else try bigger

Output

40

Complexity Analysis

Time: O(n log m) because each binary search step (log m) checks allocation in O(n) time where n is number of books and m is sum of pages

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach tries all possible max pages from max single book to sum, which is O(n*m) and very slow

Edge Cases

Single book larger than maxPages

Allocation fails immediately because no student can read that book alone

DSA Java

if (pages > maxPages) return false; // single book exceeds maxPages

Number of students equals number of books

Minimum max pages is max single book because each student can get one book

DSA Java

low = Math.max(low, pages);

Only one student

Max pages is sum of all books because one student reads all

DSA Java

high += pages;

When to Use This Pattern

When a problem asks for an optimal numeric answer within a range and checking feasibility is easier than direct calculation, use binary search on answer to efficiently find the solution.

Common Mistakes

Mistake: Setting low to 0 instead of max single book pages
Fix: Initialize low as the maximum pages in any single book to avoid invalid guesses

Mistake: Not checking if a single book exceeds mid in canAllocate
Fix: Add a guard to return false if any single book is larger than mid

Mistake: Updating low and high incorrectly causing infinite loop
Fix: Use low = mid + 1 and high = mid - 1 properly to shrink search space

Summary

It finds the smallest maximum value that satisfies a condition by guessing and checking with binary search.

Use it when you can check if a guess is valid but cannot directly compute the answer.

The key insight is to treat the answer as a search space and narrow it down by testing feasibility.

Practice

1. What is the main idea behind the Binary Search on Answer technique?

easy

A. We guess an answer and check if it satisfies the problem constraints, then adjust the guess.

B. We sort the array and then apply binary search to find an element.

C. We use binary search to find the maximum element in an unsorted array.

D. We divide the array into two halves and solve each half separately.

Solution

1. Step 1: Understand the technique's approach

   Binary Search on Answer guesses a possible answer and checks if it meets the problem's conditions.

2. Step 2: Adjust guess based on check

   If the guess is valid, we try smaller or larger guesses accordingly to find the best answer.

3. Final Answer:

   We guess an answer and check if it satisfies the problem constraints, then adjust the guess. -> Option A

4. Quick Check:

   Guess and check approach = We guess an answer and check if it satisfies the problem constraints, then adjust the guess. [OK]

Hint: Guess answer, check condition, adjust guess accordingly [OK]

Common Mistakes:

• Confusing with normal binary search on sorted arrays
• Thinking it only finds elements, not answers
• Assuming it divides data instead of answer range

2. Which of the following is the correct way to initialize the search range for binary search on answer when finding minimum maximum load among workers?

easy

A. low = 0; high = maximum single load

B. low = minimum load; high = maximum load

C. low = 0; high = sum of all loads

D. low = average load; high = sum of all loads

Solution

1. Step 1: Define search range for answer

   Minimum maximum load can be between 0 and sum of all loads because no worker can have load more than total.

2. Step 2: Set low and high accordingly

   Set low = 0 and high = sum of all loads to cover all possible answers.

3. Final Answer:

   low = 0; high = sum of all loads -> Option C

4. Quick Check:

   Search range covers all loads = low = 0; high = sum of all loads [OK]

Hint: Set low to minimum possible, high to maximum possible answer [OK]

Common Mistakes:

• Setting low to minimum load instead of 0
• Setting high to max single load instead of sum
• Using average load as boundary

3. Consider the following Java code snippet using binary search on answer to find minimum maximum pages assigned to students:

int[] pages = {10, 20, 30, 40};
int low = 40, high = 100;
while (low < high) {
  int mid = (low + high) / 2;
  if (canAllocate(pages, mid, 2)) {
    high = mid;
  } else {
    low = mid + 1;
  }
}
System.out.println(low);

// canAllocate checks if pages can be divided among 2 students with max pages mid

What will be the output?

medium

A. 70

B. 60

C. 90

D. 100

Solution

1. Step 1: Understand the problem and initial range

   Pages array is {10,20,30,40}, low=40 (max single), high=100 (sum). We want minimum max pages for 2 students.

2. Step 2: Trace binary search iterations

   Mid = 70: canAllocate true (10+20+30=60 <=70 for 1st student, 40 for 2nd). So high=70.
   Mid = 55: canAllocate false (10+20+30=60 >55). So low=56.
   Mid = 63: canAllocate true (10+20+30=60 <=63, 40 for 2nd). high=63.
   Mid = 59: canAllocate false (60 >59). low=60.
   Mid = 61: canAllocate true. high=61.
   Mid = 60: canAllocate true. high=60.
   Mid = 60 again, low=60, high=60 ends loop.

3. Final Answer:

   60 -> Option B

4. Quick Check:

   Minimum max pages = 60 [OK]

Hint: Check mid feasibility, adjust low/high until low meets high [OK]

Common Mistakes:

• Not updating low/high correctly after canAllocate
• Misunderstanding canAllocate logic
• Incorrect mid calculation or loop condition

4. The following code attempts to find the minimum largest sum of subarrays using binary search on answer. Identify the bug:

int[] nums = {7, 2, 5, 10, 8};
int m = 2;
int low = 0, high = 32;
while (low <= high) {
  int mid = (low + high) / 2;
  if (canSplit(nums, mid, m)) {
    high = mid - 1;
  } else {
    low = mid + 1;
  }
}
System.out.println(low);

// canSplit checks if nums can be split into m subarrays with max sum <= mid

medium

A. The initial low should be max element, not 0

B. The loop condition should be low < high, not low <= high

C. The mid calculation should use (low + high + 1) / 2

D. The canSplit function should return false when sum equals mid

Solution

1. Step 1: Check initial low value

   Low is set to 0, but minimum largest sum can't be less than max element (10).

2. Step 2: Correct low initialization

   Set low = max element (10) to ensure valid search range and avoid infinite loop or wrong answer.

3. Final Answer:

   The initial low should be max element, not 0 -> Option A

4. Quick Check:

   Low must start at max element [OK]

Hint: Start low at max element to avoid invalid guesses [OK]

Common Mistakes:

• Starting low at 0 causing invalid mid values
• Using wrong loop condition causing infinite loop
• Misunderstanding canSplit return values

5. You want to find the minimum time required to complete all jobs by k workers, where each job takes a certain time. Using binary search on answer, which approach correctly finds the answer? int[] jobs = {3, 6, 7, 11}; int k = 2; Options:

hard

A. Sort jobs ascending; assign jobs alternately to workers; return max load.

B. Set low = 0, high = max job time; assign jobs greedily without checking mid; return high.

C. Set low = sum of all jobs, high = max job time; use binary search to find minimum sum.

D. Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly.

Solution

1. Step 1: Define search boundaries

   Low should be max job time (11), high sum of all jobs (3+6+7+11=27) to cover all possible times.

2. Step 2: Use binary search with feasibility check

   Check if jobs can be assigned to k=2 workers within mid time. Adjust low/high based on feasibility.

3. Final Answer:

   Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly. -> Option D

4. Quick Check:

   Binary search on answer with feasibility check = Set low = max job time, high = sum of all jobs; check if jobs can be assigned within mid time using k workers; adjust low/high accordingly. [OK]

Hint: Set low=max job, high=sum; check feasibility; adjust range [OK]

Common Mistakes:

• Setting wrong low/high boundaries
• Not checking feasibility properly
• Assigning jobs without binary search