Binary Search on Answer Technique in DSA Rust

Mental Model

We guess an answer and check if it works, then adjust our guess to find the best answer quickly.

Analogy: Like guessing the weight of a box by trying different weights on a scale, narrowing down until you find the exact weight that balances it.

Range of answers: [low] -------------------- [mid] -------------------- [high]
                 ↑ guess here
Check if guess is valid, then move low or high accordingly.

Dry Run Walkthrough

Input: Find minimum maximum weight capacity to ship packages within 3 days. Packages weights: [1,2,3,4,5,6,7,8,9,10]

Goal: Find the smallest ship capacity so all packages can be shipped in 3 days.

Step 1: Set low to max package weight (10), high to sum of all weights (55), guess mid = (10+55)/2 = 32

low=10, mid=32, high=55

Why: Start with the smallest possible capacity and the largest possible capacity.

Step 2: Check if capacity 32 can ship in 3 days: group packages so sum ≤ 32 per day

Day 1: 1+2+3+4+5+6+7=28 ≤ 32
Day 2: 8+9=17 ≤ 32
Day 3: 10=10 ≤ 32

Why: Capacity 32 works because we can ship all packages in 3 days.

Step 3: Since 32 works, try smaller capacity: high = mid = 32, new mid = (10+32)/2 = 21

low=10, mid=21, high=32

Why: Try to find a smaller capacity that still works.

Step 4: Check if capacity 21 can ship in 3 days

Day 1: 1+2+3+4+5+6=21 ≤ 21
Day 2: 7+8=15 ≤ 21
Day 3: 9+10=19 ≤ 21

Why: Capacity 21 works as well.

Step 5: Try smaller capacity: high = mid = 21, new mid = (10+21)/2 = 15

low=10, mid=15, high=21

Why: Keep searching for smaller valid capacity.

Step 6: Check if capacity 15 can ship in 3 days

Day 1: 1+2+3+4+5=15 ≤ 15
Day 2: 6+7=13 ≤ 15
Day 3: 8+9=17 > 15 (fails)

Why: Capacity 15 fails because last day exceeds capacity.

Step 7: Since 15 fails, increase low: low = mid + 1 = 16, new mid = (16+21)/2 = 18

low=16, mid=18, high=21

Why: Try larger capacity to succeed.

Step 8: Check if capacity 18 can ship in 3 days

Day 1: 1+2+3+4+5=15 ≤ 18
Day 2: 6+7=13 ≤ 18
Day 3: 8+9=17 ≤ 18
Day 4: 10=10 (4 days needed, fails)

Why: Capacity 18 fails because it needs 4 days, more than allowed.

Step 9: Increase low: low = mid + 1 = 19, new mid = (19+21)/2 = 20

low=19, mid=20, high=21

Why: Try larger capacity again.

Step 10: Check if capacity 20 can ship in 3 days

Day 1: 1+2+3+4+5=15 ≤ 20
Day 2: 6+7=13 ≤ 20
Day 3: 8+9+10=27 > 20 (fail)

Why: Capacity 20 fails because last day exceeds capacity.

Step 11: Increase low: low = mid + 1 = 21, new mid = (21+21)/2 = 21

low=21, mid=21, high=21

Why: Try capacity 21 again.

Step 12: Check capacity 21 again, it works as before

Day 1: 1+2+3+4+5+6=21
Day 2: 7+8=15
Day 3: 9+10=19

Why: Capacity 21 is the smallest that works.

Result:

Final capacity: 21
Packages grouped in 3 days with max weight 21:
Day 1: 1+2+3+4+5+6=21
Day 2: 7+8=15
Day 3: 9+10=19

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    fn can_ship(weights: &[i32], capacity: i32, days: i32) -> bool {
        let mut day_count = 1;
        let mut current_load = 0;
        for &weight in weights {
            if current_load + weight > capacity {
                day_count += 1;
                current_load = weight;
                if day_count > days {
                    return false;
                }
            } else {
                current_load += weight;
            }
        }
        true
    }

    pub fn ship_within_days(weights: Vec<i32>, days: i32) -> i32 {
        let mut low = *weights.iter().max().unwrap();
        let mut high: i32 = weights.iter().sum();
        while low < high {
            let mid = low + (high - low) / 2;
            if Self::can_ship(&weights, mid, days) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        low
    }
}

fn main() {
    let weights = vec![1,2,3,4,5,6,7,8,9,10];
    let days = 3;
    let result = Solution::ship_within_days(weights, days);
    println!("{}", result);
}

for &weight in weights {

iterate over each package weight to check daily load

if current_load + weight > capacity {

if adding this package exceeds capacity, start a new day

day_count += 1;

increment day count because we need another day

if day_count > days { return false; }

if days exceed allowed days, capacity is too small

let mut low = *weights.iter().max().unwrap();

set low to max package weight as minimum capacity

let mut high: i32 = weights.iter().sum();

set high to sum of all weights as maximum capacity

while low < high {

binary search loop to narrow capacity range

if Self::can_ship(&weights, mid, days) { high = mid; } else { low = mid + 1; }

adjust search range based on feasibility of mid capacity

Output

21

Complexity Analysis

Time: O(n log m) because we do binary search over capacity range m and check feasibility in O(n) each time

Space: O(1) because we use only a few variables and no extra data structures

vs Alternative: Naive approach tries all capacities from max weight to sum, which is O(n*m) and much slower

Edge Cases

Single package

Capacity equals package weight, returns that weight

DSA Rust

let mut low = *weights.iter().max().unwrap();

Days equal to number of packages

Capacity equals max package weight because each package can be shipped alone

DSA Rust

if day_count > days { return false; }

All packages have same weight

Capacity equals package weight times packages per day

DSA Rust

if current_load + weight > capacity {

When to Use This Pattern

When you need to find an optimal numeric answer that can be checked for feasibility, use binary search on the answer range to efficiently find the best value.

Common Mistakes

Mistake: Setting low to 0 instead of max package weight
Fix: Set low to the maximum single package weight to avoid invalid capacities.

Mistake: Not updating low to mid + 1 when capacity fails
Fix: Increase low to mid + 1 to avoid infinite loops and correctly narrow the search.

Summary

Find the smallest value that satisfies a condition by guessing and checking with binary search.

Use when the answer is numeric and can be tested for feasibility efficiently.

The key is to binary search over possible answers, not over the input data.

Practice

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

easy

A. We guess an answer and use binary search to find the smallest or largest valid value.

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

C. We use binary search to find the middle element of a sorted list.

D. We apply binary search to find the maximum element in an unsorted array.

Solution

1. Step 1: Understand the technique purpose

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

2. Step 2: Use binary search to narrow answer range

   By checking mid-values and adjusting search space, we find the smallest or largest valid answer efficiently.

3. Final Answer:

   We guess an answer and use binary search to find the smallest or largest valid value. -> Option A

4. Quick Check:

   Binary Search on Answer = Guess + Check + Narrow [OK]

Hint: Think of guessing answers and checking validity with binary search [OK]

Common Mistakes:

• Confusing it with normal binary search on sorted arrays
• Thinking it finds elements, not answers
• Assuming it works only on arrays

2. Which of the following Rust code snippets correctly initializes the binary search boundaries for searching an answer between 1 and 100?

easy

A. let mut low = 0; let mut high = 101;

B. let mut low = 0; let mut high = 100;

C. let mut low = 1; let mut high = 101;

D. let mut low = 1; let mut high = 100;

Solution

1. Step 1: Identify correct search range

   The problem states searching between 1 and 100 inclusive, so low should be 1 and high 100.

2. Step 2: Check boundary initialization

   let mut low = 1; let mut high = 100; sets low = 1 and high = 100, which matches the problem range exactly.

3. Final Answer:

   let mut low = 1; let mut high = 100; -> Option D

4. Quick Check:

   Boundaries match problem range [OK]

Hint: Set low and high exactly to the problem's answer range [OK]

Common Mistakes:

• Starting low at 0 when range starts at 1
• Setting high to 101 which is outside the range
• Confusing inclusive and exclusive boundaries

3. Consider this Rust function using binary search on answer to find the minimum x such that x*x >= 10:

fn binary_search_answer() -> i32 {
    let mut low = 1;
    let mut high = 10;
    while low < high {
        let mid = (low + high) / 2;
        if mid * mid >= 10 {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    low
}

fn main() {
    println!("{}", binary_search_answer());
}

What is the output when this program runs?

medium

A. 4

B. 5

C. 10

D. 3

Solution

1. Step 1: Understand the search condition

   We want the smallest x where x*x >= 10. Squares: 3*3=9 (no), 4*4=16 (yes).

2. Step 2: Trace binary search steps

   Initial low=1, high=10 mid=5, 5*5=25 >=10, high=5 mid=3, 3*3=9 <10, low=4 mid=4, 4*4=16 >=10, high=4 Now low=4, high=4, loop ends, returns low=4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Minimum x with x*x >= 10 is 4 [OK]

Hint: Check mid squared against target, adjust low/high accordingly [OK]

Common Mistakes:

• Returning mid instead of low after loop
• Off-by-one errors in updating low or high
• Confusing condition direction (>= vs >)

4. The following Rust code tries to find the maximum x such that x*x <= 20 using binary search on answer. What is the bug?

fn max_x() -> i32 {
    let mut low = 0;
    let mut high = 20;
    while low <= high {
        let mid = (low + high) / 2;
        if mid * mid <= 20 {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    high
}

medium

A. The loop condition should be 'low < high' instead of 'low <= high'.

B. The update 'low = mid' can cause infinite loop when low == mid.

C. The function should return 'low' instead of 'high'.

D. The initial 'high' should be 21, not 20.

Solution

1. Step 1: Analyze loop update statements

   When mid equals low, setting low = mid does not change low, causing infinite loop.

2. Step 2: Identify fix for infinite loop

   To avoid infinite loop, update low to mid + 1 when condition holds.

3. Final Answer:

   The update 'low = mid' can cause infinite loop when low == mid. -> Option B

4. Quick Check:

   Update low to mid + 1 to progress loop [OK]

Hint: Always move low or high past mid to avoid infinite loops [OK]

Common Mistakes:

• Not updating low or high correctly causing infinite loops
• Returning wrong boundary after loop ends
• Confusing loop condition operators

5. You want to find the minimum time required to complete all tasks given an array of task durations and a maximum allowed time. Using binary search on answer, which approach correctly finds the minimum maximum time per worker if tasks must be assigned in order and each worker can do consecutive tasks only? Choose the correct high-level approach.

hard

A. Use binary search to find the worker count, then assign tasks randomly.

B. Sort tasks and binary search for the task with maximum duration to assign first.

C. Binary search the answer range of time, and for each mid, greedily assign tasks to workers checking if all tasks fit within mid time.

D. Apply binary search on the number of tasks, splitting tasks evenly among workers.

Solution

1. Step 1: Define answer range and check function

   We binary search over possible maximum time per worker. For each mid, we check if tasks can be assigned in order without exceeding mid time per worker.

2. Step 2: Greedy assignment check

   Assign tasks to workers greedily, moving to next worker when current sum exceeds mid. If all tasks fit within allowed workers, mid is valid.

3. Final Answer:

   Binary search the answer range of time, and for each mid, greedily assign tasks to workers checking if all tasks fit within mid time. -> Option C

4. Quick Check:

   Binary Search on Answer + Greedy check = Correct approach [OK]

Hint: Binary search answer, check feasibility with greedy assignment [OK]

Common Mistakes:

• Sorting tasks when order matters
• Binary searching worker count instead of time
• Assigning tasks randomly ignoring order