Chapter 6: Sorting & Searching

6.1 Sorting: More Than Just Ascending Order

Chapter 3 introduced std::sort. In contests, you rarely implement quicksort or merge sort by hand—except when the problem specifically asks for inversions.

The battlefield focus is sorting structs.

6.1.1 Custom Comparator

Scenario: You have N students, each with a score and an ID. Sort them by score descending. If two scores tie, sort by ID ascending.

This is a typical multi-key sort. You write a cmp function to tell sort how to order the elements.

struct Student {
    int id;
    int score;
};
 
bool cmp(const Student &a, const Student &b) {
    if (a.score != b.score) {
        return a.score > b.score; // higher scores come first
    }
    return a.id < b.id; // smaller ID wins on ties
}
 
// In main:
// vector<Student> students;
sort(students.begin(), students.end(), cmp);

💡 Modern C++ lets you use lambdas directly inside sort: sort(v.begin(), v.end(), [](Student a, Student b) { ... });

6.2 Binary Search: The Magic Halving Technique

Binary search halves the search range each time, reducing N to log2 N. Even if N = 10^{18}, you only probe ~60 times.

6.2.1 Basic Binary Search

This is the staple: find a value in a sorted array. STL provides lower_bound, but you still have to write manual binary search for more complicated logic.

6.2.2 Binary Search on the Answer

This is the core of this chapter. Many problems look nothing like search problems but really ask you to guess an answer.

Key property: the answer is monotonic.

• Example: if speed X is enough to finish a task, then any speed > X will also work.
• The questions usually ask to maximize the minimum or minimize the maximum.

Template: assume the answer is mid, and write check(mid) to verify feasibility.

long long l = 0, r = 1e9, ans = -1;
while (l <= r) {
    long long mid = l + (r - l) / 2; // avoid overflow
    if (check(mid)) {
        ans = mid;
        l = mid + 1; // try to go higher (for max)
    } else {
        r = mid - 1; // mid is too big (assuming monotonicity)
    }
}
cout << ans << endl;

Example: Woodcutting (P2440)

Problem: You have N logs of varying lengths. Cut them into K equal-length pieces. Maximize the piece length.

Idea: If length 10cm works, any smaller length works as well. Binary search mid (the candidate piece length). In check(mid), count how many pieces each log yields. If the total ≥ K, mid is feasible (record it and try larger); otherwise mid is too long.

6.3 Two Pointers: Clever O(N)

Some problems ask you to find two elements or a range. A naive double loop is O(N^2), but two pointers bring it down to O(N).

6.3.1 Opposing Pointers (Two Ends)

Scenario: In a sorted array, find two numbers whose sum equals Target.

• L starts at the left, R at the right.
• If arr[L] + arr[R] > Target, move R left (sum decreases).
• If arr[L] + arr[R] < Target, move L right (sum increases).
• Repeat until L == R.
• Efficiency: each element is visited at most once ⇒ O(N).

6.3.2 Sliding Window / Caterpillar Method

Scenario: Find the shortest contiguous subarray whose sum is ≥ S.

• Imagine a caterpillar crawling along the array.

1. Extend the head: move the right pointer R to add new elements.
2. Shrink the tail: when the sum is ≥ S, move the left pointer L to try to shorten the range while keeping the sum valid.

6.4 Discretization: Optional but Powerful

When the values are huge (e.g., up to 10^9) but there are only N ≈ 10^5 numbers, and you only care about relative order, you can map them to ranks (1, 2, ..., N) so you can use them as array indices.

Steps:

1. Copy all values into a vector.
2. Sort and deduplicate.
3. Use lower_bound to find the rank (1-based index) of the original number.

vector<int> a = {100000, 20, 9999999, 20};
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
 
int rank = lower_bound(b.begin(), b.end(), 9999999) - b.begin() + 1; // rank = 3

🧠 Chapter Summary & Practice

Sorting conquers disorder, binary search speeds up lookups, and two pointers avoid redundant scans. Together, they form the backbone of O(N log N) and O(N) solutions.

Exercises:

1. P2249 [Deep Foundation 13.1] Search (Luogu): basic binary search practice.
2. P1873 EKO / Cutting Trees (COCI 2011/2012 #5): classic binary search-on-answer problem.
3. P1102 A-B Number Pairs: solve it three different ways—sorting + binary search, maps, and two pointers—to understand trade-offs.

You now know most of the techniques for handling one-dimensional arrays. Next, if your math teacher asks about GCD or sieving primes, what will you say?