I. In-Class Exercises

Programming Exercises

1. Sequence Partitioning: L3141
2. Lumberjack: L3142

II. Knowledge Summary

✨ Core Idea

Binary Search on Answer (Binary Search the Answer) is an extended application of the binary search algorithm, used to solve optimization problems, particularly when the possible answers can be arranged in order and a "yes or no" judgment can be made. This technique is typically used to find the optimal solution in a continuous or discrete ordered space.

The core of this technique lies in using the binary search idea to continuously narrow the range of possible answers and quickly converge on the target solution. This method requires the solution space to have monotonicity, meaning the validity of solutions is monotonic (non-increasing or non-decreasing), so the direction of narrowing the search range can be clearly determined.

✨ Algorithm Principle

The specific execution steps of Binary Search on Answer are as follows:

1. Determine the range: First, determine the minimum value low and maximum value high of the possible answer. The range is determined based on the problem statement — typically low is the minimum allowed value and high is the maximum allowed value.
2. Midpoint judgment: Calculate the midpoint mid = (low + high) / 2, then use a check function to verify whether mid is a feasible solution. The check function is the key to Binary Search on Answer and should complete the judgment in O(n) or better time.
3. Adjust the range:
   • If mid is a feasible solution, adjust low or high based on the problem's requirements (finding the minimum or maximum):
     • If we need the smallest feasible solution and mid is feasible, set high to mid
     • If we need the largest feasible solution and mid is feasible, set low to mid + 1
   • If mid is not feasible, adjust low or high in the opposite direction
4. Repeat the process: Repeat the above process until the interval between low and high is small enough to satisfy the condition (usually when low and high meet).

✨ Application Scenarios

Common application scenarios for Binary Search on Answer include:

• Capacity minimization problems: For example, determining the minimum ship capacity so that all cargo can be transported within a limited number of trips
• Speed maximization problems: Finding the maximum speed such that at this speed or lower, the time to complete a task is still acceptable
• Economic/cost problems: Finding the minimum investment amount to achieve the expected profit or effect

The common characteristic of these problems is: the larger (or smaller) the answer, the easier (or harder) the condition is to satisfy, exhibiting clear monotonicity.

✨ Code Implementation

Here is an example using Binary Search on Answer technique to solve a search problem, demonstrating finding the first and last positions equal to the target value:

1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int findFirst(const vector<int>& nums, int target) {
7    int low = 0, high = nums.size() - 1;
8    int first = -1;
9    while (low <= high) {
10        int mid = low + (high - low) / 2;
11        if (nums[mid] >= target) {
12            if (nums[mid] == target) first = mid;
13            high = mid - 1;
14        } else {
15            low = mid + 1;
16        }
17    }
18    return first;
19}
20
21int findLast(const vector<int>& nums, int target) {
22    int low = 0, high = nums.size() - 1;
23    int last = -1;
24    while (low <= high) {
25        int mid = low + (high - low) / 2;
26        if (nums[mid] <= target) {
27            if (nums[mid] == target) last = mid;
28            low = mid + 1;
29        } else {
30            high = mid - 1;
31        }
32    }
33    return last;
34}
35
36int main() {
37    vector<int> nums = {1, 2, 4, 4, 4, 5, 6};
38    int target = 4;
39    cout << "First Position: " << findFirst(nums, target) << endl;
40    cout << "Last Position: " << findLast(nums, target) << endl;
41    return 0;
42}

✨ Execution Example

Using the classic "Lumberjack" problem as an example: There are n trees with heights h1, h2, ..., hn. The lumberjack sets a sawblade height H, and all trees taller than H are cut at height H. Find the maximum H such that "at least M meters of wood are obtained."

Sample data: 4 trees with heights [20, 15, 10, 17], needing at least 7 meters of wood.

Monotonicity analysis: The lower H is, the more wood is obtained; the higher H is, the less wood is obtained. So we want to find the maximum H such that the wood amount >= 7.

Check function: Given H, wood amount = sum(max(0, hi - H))

Binary search process: low=0, high=20 (the tallest tree)

Final answer: H = 15, which yields exactly 7 meters of wood.

✨ Detailed Problem-Solving Steps

When encountering Binary Search on Answer problems, follow these steps to analyze:

1. Identify the problem type: If the problem asks to "maximize a value such that a condition is satisfied" or "minimize a value such that a condition is satisfied," it is likely Binary Search on Answer.
2. Verify monotonicity: Confirm that as the answer increases (or decreases), the condition becomes easier (or harder) to satisfy. Binary search is only effective when monotonicity holds.
3. Determine the binary search range: Analyze the minimum and maximum possible values of the answer. These can usually be derived from the data range given in the problem.
4. Write the check function: This is the most critical step. Given a candidate answer mid, determine whether it is feasible in O(n) time.
5. Determine the binary search direction:
   • Finding the maximum feasible value: When mid is feasible, low = mid + 1; when not feasible, high = mid - 1; record the answer when feasible.
   • Finding the minimum feasible value: When mid is feasible, high = mid - 1; when not feasible, low = mid + 1; record the answer when feasible.
6. Watch for integer/floating-point: If the answer is an integer, use standard integer binary search. If the answer is a floating-point number, change the loop condition to high - low > 1e-6 (precision requirement).

✨ Common Mistakes

• Incorrect monotonicity judgment: If the problem does not have monotonicity, Binary Search on Answer is not applicable. Before using it, you must confirm that "as the answer increases, the satisfaction of the condition changes monotonically."
• Binary search range set too small: If high is not set large enough, the correct answer may be excluded. It is recommended to set the range generously.
• Incorrect check function: The correctness of the check function directly determines the final answer. It is recommended to test the check function separately to ensure it handles edge cases correctly.
• Confusing the logic for finding maximum vs. minimum: This is the most common mistake in Binary Search on Answer. When finding the maximum feasible value, feasibility should shift low to the right; when finding the minimum feasible value, feasibility should shift high to the left.
• Infinite loop in integer binary search: When low + 1 == high, mid = (low + high) / 2 = low. If at this point low = mid (instead of low = mid + 1), it will cause an infinite loop.

III. Homework

Programming Exercises

1. Angry Cows (USACO): L3143