GESP C++ Level 5 Exam Outline Knowledge Points Review: (6) Binary Search and Binary Answer

In the official GESP C++ Level 5 exam outline, there are a total of 9 key points. This article focuses on the analysis and introduction of the 6th key point.

(6) Master the basic principles of the binary search and binary answer algorithms (also known as binary enumeration method), and be able to quickly locate the target value in a sorted array.

I am also learning, experimenting, and summarizing, and my grasp of the depth and breadth of the exam outline is based on personal understanding. Therefore, this article is more of a personal knowledge review rather than a tutorial. If there are any omissions or oversights, please feel free to correct and discuss.

Review of other Level 5 key points:

GESP C++ Level 5 Exam Outline Knowledge Points Review: (1) Elementary Number Theory
GESP C++ Level 5 Exam Outline Knowledge Points Review: (2) Simulating High-Precision Calculations
GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-1) Linked Lists – Singly Linked List
GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-2) Linked Lists – Doubly Linked List
GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-3) Linked Lists – Singly Circular Linked List
GESP C++ Level 5 Exam Outline Knowledge Points Review: (3-4) Linked Lists – Doubly Circular Linked List
GESP C++ Level 5 Exam Outline Knowledge Points Review: (4) Euclidean Algorithm, Prime Table, and Uniqueness Theorem
GESP C++ Level 5 Exam Outline Knowledge Points Review: (5) Algorithm Complexity Estimation (Polynomial, Logarithmic)

In algorithm learning, the binary method is a very classic idea. Its core is to continuously halve the problem size until the answer is found or the range of the answer is determined. The binary method is not only used for searching specific values but is often used to solve some optimization problems with monotonicity. We usually refer to the former as binary search and the latter as binary answer or binary enumeration method.

GESP Level 1 Practice Question List
GESP Level 1 Real Question List
GESP Level 2 Practice Question List
GESP Level 2 Real Question List
GESP Level 3 Practice Question List
GESP Level 3 Real Question List
GESP Level 4 Practice Question List
GESP Level 4 Real Question List
GESP Level 1-5 Exam Outline Analysis

1. Basic Principles of Binary Search

1.1 Preconditions

Binary search requires the data sequence to be sorted. Only in a sorted array can we determine whether the target value should fall in the left half or the right half by comparing the middle value.

1.2 Basic Idea

Set the search interval [L, R]:

Take the midpoint mid = (L + R) / 2.
Compare a[mid] with the target value x:

If a[mid] == x, the target is found.
If a[mid] < x, it indicates the target is in the right half, update the interval to [mid+1, R].
If a[mid] > x, it indicates the target is in the left half, update the interval to [L, mid-1].

Continuously narrow the interval until the target value is found or the interval is empty.

1.3 Time Complexity

Since each operation will halve the interval, the time complexity is

far superior to sequential search.

1.4 Example of Binary Search Problem

1.4.1 Problem Description

In a sorted array, given a target value x, please use binary search to determine whether the target value exists. If it exists, output its index; otherwise, output -1.

For example:

Array:[1, 3, 5, 7, 9, 11]
Target:7
Result:3 (since the index starts from 0, a[3] = 7)

1.4.2 C++ Code Example

#include <iostream>
#include <vector>
using namespace std;

// Binary search function
int binary_search(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid overflow
        if (arr[mid] == target) {
            return mid; // Target found
        } else if (arr[mid] < target) {
            left = mid + 1; // Target is on the right
        } else {
            right = mid - 1; // Target is on the left
        }
    }
    return -1; // Not found
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target;
    cout << "Please enter the number to search: ";
    cin >> target;

    int result = binary_search(arr, target);
    if (result != -1) {
        cout << "Target " << target << " found at index " << result << endl;
    } else {
        cout << "Target " << target << " does not exist in the array" << endl;
    }
    return 0;
}

Running Effect:

Input:

Output:

Target 7 found at index 3

Input:

Output:

Target 8 does not exist in the array

2. Basic Principles of Binary Answer

Binary search is mainly for locating a specific value, while the idea of binary answer is more inclined to finding the optimal solution that meets certain conditions.

2.1 Applicable Scenarios

When the answer to a problem lies within a certain interval and satisfies a certain monotonicity, binary answer can be used.

Monotonicity means that if a certain value satisfies the condition, all values greater (or smaller) than this value also satisfy (or do not satisfy) the condition. For example:

Finding the maximum load: If a truck can carry 100kg, it can certainly carry 50kg as well.
Finding the minimum cost: If 100 yuan is not enough to buy the required items, then 80 yuan will certainly not be enough either.

2.2 Basic Steps

Determine the search range for the answer [L, R].
Take the midpoint mid, and design a decision function check(mid) to determine whether this answer is feasible.
Based on the result of check(mid), decide which half of the interval to keep:

If mid is feasible, continue to try for a better solution;
If mid is not feasible, expand or shrink the range.

The final L or R will be the optimal solution.

2.3 Key Points

Monotonicity of the interval: The answer must have the characteristic that “if a certain value is feasible, then larger/smaller values are also feasible or infeasible”.
Design of the decision function: How to determine whether a candidate answer meets the requirements is the key to binary answer.

2.4 Example of Binary Answer Problem

2.4.1 Problem Description

Given a positive integer arraynums (length n), and an integer m. You need to divide nums into m continuous subarrays (each subarray cannot be empty).

Definition: Each subarray has a “sum” (i.e., the total sum of all numbers in it), and the largest of these m subarrays is called the maximum subarray sum.

Goal: Minimize this “maximum subarray sum” and return its minimum value.

Input and Output Format

Input: Array nums and an integer m
Output: An integer representing the minimum maximum subarray sum

Example

For example, input:

nums = [7, 2, 5, 10, 8], m = 2

Possible partitioning:

[7,2,5] and [10,8]

Subarray sums: 14, 18
Maximum = 18

[7,2] and [5,10,8]

Subarray sums: 9, 23
Maximum = 23

[7] and [2,5,10,8]

Subarray sums: 7, 25
Maximum = 25

Among all partitioning methods, the smallest maximum value is 18.

Output:

2.4.2 Thought Analysis

Analyze the characteristics of the problem

Need to divide the array into m continuous subarrays
Each subarray has a sum
The goal is to minimize the maximum subarray sum

Find the direction to solve the problem

If we directly enumerate all partitioning schemes, the complexity will be very high
Notice that the subarray sum has a characteristic: if a certain value can be the maximum subarray sum, then any value larger than it can also be
This monotonicity suggests that we can use binary answer

Determine the search range

Minimum possible value: the maximum element in the array (because any partitioning scheme must include this element)
Maximum possible value: the sum of the entire array (i.e., the case of only one segment)

Design the decision function

Given a candidate value for the maximum subarray sum maxSum
Determine whether the array can be divided into no more than m subarrays, such that each subarray’s sum does not exceed maxSum
Greedily scan from left to right, trying to put as many numbers as possible into the current subarray
If the number of segments exceeds m, it indicates that the current maxSum is too small

Binary Search Process

If feasible, it indicates that the answer may be smaller, update right = mid - 1
If not feasible, it indicates that the answer must be larger, update left = mid + 1

Initialize the left boundary left = max(nums) (the maximum value in the array)
Initialize the right boundary right = sum(nums) (the sum of the entire array)
Each time take the midpoint mid = (left + right) / 2
Call the decision function check(mid):
Finally, left will be the answer

Time Complexity Analysis

Number of binary search iterations:
Each decision requires traversing the array:
Total time complexity:

This problem-solving process demonstrates the typical characteristics of binary answer:

Transforming optimization problems into decision problems
Using the monotonicity of the answer for binary search
Continuously narrowing the range to approach the optimal solution

2.4.3 C++ Code Example

#include <iostream>     // Input and output stream
#include <vector>       // Using vector container
#include <numeric>      // Using accumulate function
#include <algorithm>    // Using max_element function
using namespace std;

// Decision function: Given the maximum subarray sum maxSum, can it be divided into <= m segments
bool check(vector<int>& nums, int m, long long maxSum) {
    long long curSum = 0;   // Current subarray sum
    int count = 1;          // At least one segment
    
    for (int num : nums) {  // Traverse each element in the array
        if (curSum + num > maxSum) {  // If adding the current number exceeds the maximum sum
            count++;                   // Increase the number of segments
            curSum = num;              // Start a new segment
            
            if (count > m) {
                return false;          // More segments than m, not feasible
            }
        } else {
            curSum += num;             // Current number can be added to the current segment
        }
    }
    
    return true;            // Number of segments did not exceed m, feasible scheme
}

int splitArray(vector<int>& nums, int m) {
    // Initialize the left and right boundaries for binary search
    long long left = *max_element(nums.begin(), nums.end());    // Left boundary is the maximum value in the array
    long long right = accumulate(nums.begin(), nums.end(), 0LL); // Right boundary is the total sum of the array
    long long ans = right;  // Initialize the answer to the right boundary

    // Binary search process
    while (left <= right) {
        long long mid = left + (right - left) / 2;  // Calculate the midpoint, avoid overflow
        if (check(nums, m, mid)) {     // If the current maximum sum is feasible
            ans = mid;                  // Update the answer
            right = mid - 1;            // Try smaller values
        } else {
            left = mid + 1;            // Current value is too small, needs to increase
        }
    }
    return ans;             // Return the final answer
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};  // Test array
    int m = 2;                            // Number of segments to divide into
    cout << "The minimum maximum subarray sum is: " << splitArray(nums, m) << endl;
    return 0;
}

Output Result:

The minimum maximum subarray sum is: 18

3. Comparison Summary of Binary Search and Binary Answer

Feature	Binary Search	Binary Answer
Goal	Find specific value	Find optimal solution
Precondition	Sorted array	Answer has monotonicity
Decision	Compare with target value	Custom decision function
Application	Array search, positioning	Queuing, allocation, optimization problems

In summary, the essence of the binary method lies in “halving and quickly locating“.

In a sorted array, binary search can find the target value in time.
In problems where the answer interval has monotonicity, binary answer can quickly solve the optimal solution through the “guess answer + decision function” method.

Mastering binary search and binary answer not only enhances algorithm efficiency but also lays a solid foundation for solving more complex optimization problems.

For details on GESP exam outlines, real questions explanations, knowledge expansion, and practice lists, see:

[Pinned] GESP C++ Certification Learning Resource Summary

Problems in the “luogu-” series can be evaluated online in the Luogu Problem Bank.

Problems in the “bcqm-” series can be evaluated online in the Programming Enlightenment Problem Bank.

1. Basic Principles of Binary Search

1.1 Preconditions

1.2 Basic Idea

1.3 Time Complexity

1.4 Example of Binary Search Problem

1.4.1 Problem Description

1.4.2 C++ Code Example

2. Basic Principles of Binary Answer

2.1 Applicable Scenarios

2.2 Basic Steps

2.3 Key Points

2.4 Example of Binary Answer Problem

2.4.1 Problem Description

Input and Output Format

Example

2.4.2 Thought Analysis

2.4.3 C++ Code Example

3. Comparison Summary of Binary Search and Binary Answer

Related posts

Leave a Comment Cancel reply