Chapter 3.3: Sorting & Searching

📝 Before You Continue: You should be comfortable with arrays, vectors, and basic loops (Chapters 2.2–2.3). Familiarity with std::sort from Chapter 3.1 helps, but this chapter covers it in depth.

Sorting and searching are two of the most fundamental operations in computer science. In USACO, a huge fraction of problems become easy once you sort the data correctly. And binary search — the ability to search a sorted array in O(log n) — is a technique you'll reach for again and again.

3.3.1 Why Sorting Matters

Consider this problem: "Given N cow heights, find the two cows whose heights are closest together."

• Unsorted approach: Compare every pair → O(N²). For N = 10^5, that's 10^10 operations. TLE.
• Sorted approach: Sort the heights → O(N log N). Then the closest pair must be adjacent! Check N-1 pairs → O(N). Total: O(N log N). ✓

💡 Key Insight: Sorting transforms many O(N²) brute-force solutions into O(N log N) or O(N) solutions. When you see "find the pair with property X" or "find the minimum/maximum of something involving two elements," always consider sorting first.

Complexity Analysis:

• Sorting: O(N log N) time, O(log N) space (recursion stack depth; std::sort uses Introsort — a hybrid of Quicksort + Heapsort + Insertion Sort — all three branches use at most O(log N) stack space)
• After sorting: adjacent comparisons or two-pointer techniques are O(N)

3.3.2 How Sorting Works (Conceptual)

You don't need to implement sorting algorithms yourself — std::sort does it for you. But understanding the ideas helps you reason about time complexity and choose the right approach.

Here are four classic sorting algorithms, each with an interactive visualization to help you understand how they work.

🫧 Bubble Sort — O(N²)

Repeatedly scan the array, swapping adjacent elements that are out of order. Each pass "bubbles" the current maximum to its final position at the end of the unsorted region:

Initial: [64, 34, 25, 12, 22, 11, 90]
Pass 1:  [64, 34, 25, 12, 22, 11, 90] → [34, 25, 12, 22, 11, 64, 90]   ← 64 bubbles to 2nd-to-last
Pass 2:  [34, 25, 12, 22, 11, 64, 90] → [25, 12, 22, 11, 34, 64, 90]   ← 34 bubbles to 3rd-to-last
Pass 3:  [25, 12, 22, 11, 34, 64, 90] → [12, 22, 11, 25, 34, 64, 90]   ← 25 bubbles to 4th-to-last
...

📝 Note: 90 was already in its correct position at the start, so Pass 1 doesn't move it — instead, 64 (the next largest) bubbles to the second-to-last position. Each pass guarantees one more element is in its final sorted position at the end.

Bubble sort is O(N²). Never use it on large inputs in competitive programming. We cover it only because it's conceptually the simplest.

🃏 Insertion Sort — O(N²) / O(N) best case

Divide the array into a left "sorted region" and a right "unsorted region." Each step takes the first element of the unsorted region and inserts it into the correct position in the sorted region:

Start: [64 | 34, 25, 12, 22, 11, 90]   ← | sorted on left
i=1:   [34, 64 | 25, 12, 22, 11, 90]   ← 34 inserted before 64
i=2:   [25, 34, 64 | 12, 22, 11, 90]   ← 25 inserted at front
i=3:   [12, 25, 34, 64 | 22, 11, 90]   ← 12 inserted at front
...

💡 Insertion sort's strength: Very fast on nearly-sorted arrays (approaches O(N)). std::sort switches to insertion sort for small subarrays.

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];   // element to insert
        int j = i - 1;
        // shift elements greater than key one position to the right
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // place key in its correct position
    }
}

🔀 Merge Sort — O(N log N) always

Divide and conquer: recursively split the array in half, then merge the two sorted halves back together:

[38, 27, 43, 3, 9, 82, 10]
        ↓ split recursively
[38,27,43,3]    [9,82,10]
[38,27] [43,3]  [9,82] [10]
[38][27][43][3] [9][82][10]
        ↓ merge bottom-up
[27,38] [3,43]  [9,82] [10]
  [3,27,38,43]    [9,10,82]
      [3,9,10,27,38,43,82] ✓

Merge sort is O(N log N) in all cases and is a stable sort.

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(a.begin() + lo, a.begin() + hi + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (tmp[i - lo] <= tmp[j - lo]) {
            a[k++] = tmp[i - lo];  // 左半部分当前元素更小，优先放入以保持稳定性
            i++;
        } else {
            a[k++] = tmp[j - lo];  // 右半部分当前元素更小，放入
            j++;
        }
    }
    while (i <= mid) { a[k++] = tmp[i - lo]; i++; }  // 追加左半部分剩余元素
    while (j <= hi)  { a[k++] = tmp[j - lo]; j++; }  // 追加右半部分剩余元素
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);       // sort left half
    mergeSort(a, mid + 1, hi);   // sort right half
    merge(a, lo, mid, hi);       // merge two sorted halves
}

⚡ Quicksort — O(N log N) average

Quicksort is one of the core algorithms underlying std::sort. Its key idea is divide and conquer:

1. Pick a pivot element (typically the last element)
2. Partition: move all elements ≤ pivot to the left, all > pivot to the right; pivot lands in its final position
3. Recurse on the left and right subarrays

[8, 3, 6, 1, 9, 2, 7, 4]   ← pivot = 4
         ↓ partition
[3, 1, 2, 4, 9, 6, 7, 8]   ← 4 in final position; left ≤ 4, right > 4
 ↑_______↑  ↑  ↑__________↑
 left subarray  right subarray

Recurse on [3,1,2] → [1,2,3]
Recurse on [9,6,7,8] → [6,7,8,9]

Final: [1, 2, 3, 4, 6, 7, 8, 9] ✓

// Partition arr[lo..hi] using last element as pivot.
// Returns the final index of the pivot.
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];   // choose last element as pivot
    int i = lo - 1;        // i points to end of "≤ pivot" region

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // bring arr[j] into ≤ pivot region
        }
    }
    swap(arr[i + 1], arr[hi]);  // place pivot in its final position
    return i + 1;               // return pivot's index
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;           // base case: subarray length ≤ 1
    int p = partition(arr, lo, hi); // p is pivot's final position
    quickSort(arr, lo, p - 1);      // sort left subarray
    quickSort(arr, p + 1, hi);      // sort right subarray
}

⚠️ Worst case: If the pivot is always the max or min (e.g., already-sorted input), recursion depth degrades to O(N) and total time becomes O(N²). std::sort avoids this via random pivot selection or median-of-three, guaranteeing O(N log N) worst case.

3.3.3 std::sort in Practice

⚠️ Stability Note: std::sort is NOT stable — it uses Introsort (Quicksort + Heapsort + Insertion sort hybrid), which does not preserve the relative order of equal elements. If you need stable sorting, use std::stable_sort instead (see the comparison table in this section).

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    // Sort ascending
    sort(v.begin(), v.end());

    // Sort descending
    sort(v.begin(), v.end(), greater<int>());

    // Sort only part of a vector (indices 2 through 5 inclusive)
    sort(v.begin() + 2, v.begin() + 6);

    for (int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

Sorting by Multiple Criteria

Often you want to sort by one field, and break ties with another. With pair, this is automatic (sorts by .first, then .second):

vector<pair<int, string>> students;
students.push_back({85, "Alice"});
students.push_back({92, "Bob"});
students.push_back({85, "Charlie"});

sort(students.begin(), students.end());
// Result: {85, "Alice"}, {85, "Charlie"}, {92, "Bob"}
// Sorted by score first, then alphabetically by name

Custom Comparators

A comparator is a function that returns true if the first argument should come before the second in the sorted order.

The clearest way to write a comparator is as a standalone function:

struct Cow {
    string name;
    int weight;
    int height;
};

// Sort by weight ascending; break ties by height descending
bool cmpCow(const Cow &a, const Cow &b) {
    if (a.weight != b.weight) return a.weight < b.weight;  // lighter first
    return a.height > b.height;                             // taller first (tie-break)
}

int main() {
    vector<Cow> cows = {{"Bessie", 500, 140}, {"Elsie", 480, 135}, {"Moo", 500, 138}};

    sort(cows.begin(), cows.end(), cmpCow);

    for (auto &c : cows) {
        cout << c.name << " " << c.weight << " " << c.height << "\n";
    }
    // Output:
    // Elsie 480 135
    // Bessie 500 140
    // Moo 500 138
    return 0;
}

💡 Style Note: Defining cmp as a standalone function (rather than an inline lambda) makes the sorting logic easier to read, test, and reuse — especially when the comparison involves multiple fields.

Sorting Algorithm Stability

⚠️ Important: std::sort is NOT stable — equal elements may appear in any order after sorting. Use std::stable_sort if relative order of equal elements must be preserved.

Sorting Algorithm Stability Comparison

📝 Note: std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort). Because Quicksort is not stable, std::sort makes no guarantee on the relative order of equal elements. When you sort students by score and need students with the same score to remain in their original order, use std::stable_sort.

* std::stable_sort is O(N log N) when sufficient extra memory (O(N)) is available. It degrades to O(N log² N) only when memory is limited and in-place merging is required.

Visual: Sorting Algorithm Comparison

This chart compares the time complexity, space usage, and stability of common sorting algorithms, helping you choose the right one for each situation.

Counting Sort — O(N+K) for Small Value Ranges

When values are bounded integers in a small range [0, MAXVAL], counting sort beats std::sort by a wide margin:

// Counting sort: for integers in range [0, MAXVAL]
// Time O(N+MAXVAL), stable sort
void countingSort(vector<int>& arr, int maxVal) {
    vector<int> cnt(maxVal + 1, 0);
    for (int x : arr) cnt[x]++;
    int idx = 0;
    for (int v = 0; v <= maxVal; v++)
        for (int i = 0; i < cnt[v]; i++) arr[idx++] = v;  // 用 for 循环避免 cnt[v] 被减为 -1 的副作用
}
// USACO use case: faster than std::sort when value range is small (e.g., cow IDs 1-1000)

When to use counting sort in USACO:

• Cow IDs in range [1, 1000], N = 10^6 → counting sort is O(N + 1000) vs O(N log N)
• Grade values [0, 100] → trivially fast
• Color categories [0, 3] → instant

Caution: If MAXVAL is large (e.g., 10^9), counting sort requires O(MAXVAL) memory — don't use it. Coordinate compress first (Section 3.3.6), then count.

3.3.4 Binary Search

Binary search finds a target in a sorted array in O(log n) — instead of O(n) for linear search.

Analogy: Searching for a word in a dictionary. You don't start from A and read every entry — you open to the middle, check if your word is before or after, then repeat. Each step cuts the search space in half: after k steps, you've gone from N candidates to N/2^k. When N/2^k < 1, you're done — that takes k = log₂(N) steps.

💡 Key Insight: Binary search works whenever you have a monotone predicate — a condition that is false false false ... true true true (or the reverse). You can binary search for the boundary between false and true in O(log N).

Visual: Binary Search in Action

The diagram above shows a single-step binary search finding 7 in [1,3,5,7,9,11,13]. The left (L), right (R), and mid (M) pointers are shown. The key insight: computing mid = left + (right - left) / 2 avoids integer overflow compared to (left + right) / 2.

Manual Binary Search

// Solution: Binary Search — O(log N)
#include <bits/stdc++.h>
using namespace std;

// Returns index of target in sorted arr, or -1 if not found
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // ← KEY LINE: avoid overflow (don't use (lo+hi)/2)

        if (arr[mid] == target) {
            return mid;         // found!
        } else if (arr[mid] < target) {
            lo = mid + 1;       // target is in the right half
        } else {
            hi = mid - 1;       // target is in the left half
        }
    }

    return -1;  // not found
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << binarySearch(v, 7) << "\n";   // 3 (index)
    cout << binarySearch(v, 6) << "\n";   // -1 (not found)
    return 0;
}

Step-by-step trace for searching 7 in [1, 3, 5, 7, 9, 11, 13, 15]:

lo=0, hi=7: mid=3, arr[3]=7 → FOUND at index 3 ✓

Searching for 6:
lo=0, hi=7: mid=3, arr[3]=7 > 6 → hi=2
lo=0, hi=2: mid=1, arr[1]=3 < 6 → lo=2
lo=2, hi=2: mid=2, arr[2]=5 < 6 → lo=3
lo=3 > hi=2: loop ends → return -1 ✓

Why lo + (hi - lo) / 2? If lo and hi are both large (close to INT_MAX), then lo + hi overflows! This formula is equivalent but safe.

The STL Way: lower_bound and upper_bound

These are almost always what you actually want in competitive programming:

// STL Binary Search Operations — all O(log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};

    // lower_bound: iterator to first element >= target
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << *lb << "\n";                    // 3 (first 3)
    cout << lb - v.begin() << "\n";         // 1 (index)

    // upper_bound: iterator to first element > target
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << *ub << "\n";                    // 5 (first element after all 3s)
    cout << ub - v.begin() << "\n";         // 3 (index)

    // Count occurrences: upper_bound - lower_bound
    int count_of_3 = upper_bound(v.begin(), v.end(), 3)
                   - lower_bound(v.begin(), v.end(), 3);
    cout << count_of_3 << "\n";   // 2

    // Check if value exists
    bool exists = binary_search(v.begin(), v.end(), 7);
    cout << exists << "\n";  // 1

    // Find largest value <= target (floor)
    auto it = upper_bound(v.begin(), v.end(), 6);
    if (it != v.begin()) {
        --it;
        cout << *it << "\n";  // 5 (largest value <= 6)
    }

    return 0;
}

⚠️ Common Mistake: Using lower_bound/upper_bound on an unsorted container. These functions assume sorted order — on unsorted data, they give wrong results with no error!

3.3.5 Binary Search on the Answer

This is one of the most powerful and commonly-tested techniques in USACO Silver. The idea:

Instead of searching for a value in an array, binary search over the answer space itself.

When does this apply? When:

1. The answer is a number in some range [lo, hi]
2. There's a function canAchieve(X) that checks if X is feasible
3. The function is monotone: if X works, all values ≤ X also work (or all ≥ X work)

💡 Key Insight: Monotonicity means there's a "threshold" separating feasible from infeasible answers. Binary search finds this threshold in O(log(hi-lo)) calls to canAchieve. If each call takes O(f(N)), total time is O(f(N) × log(answer_range)).

Classic Example: Aggressive Cows (SPOJ AGGRCOW / Classic Problem)

Problem: N stalls at positions p[1..N], place C cows to maximize the minimum distance between any two cows.

Why binary search? If we can place cows with minimum gap D, we can also place them with gap D-1. So feasibility is monotone: there's a threshold D* where ≥ D* is infeasible and < D* is feasible. We binary search for D*.

The canPlace(minDist) function: Place the first cow at the leftmost stall, then greedily pick the next stall that is at least minDist away. Count how many cows we can place this way — if ≥ C, return true.

// Solution: Binary Search on Answer — O(N log N log(max_distance))
#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> stalls;

// Can we place c cows such that the minimum gap between any two cows is >= minDist?
bool canPlace(int minDist) {
    int placed = 1;           // place first cow at stall 0
    int lastPos = stalls[0];  // position of last placed cow

    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPos >= minDist) {  // this stall is far enough
            placed++;
            lastPos = stalls[i];
        }
    }
    return placed >= c;  // did we place all c cows?
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> c;
    stalls.resize(n);
    for (int &x : stalls) cin >> x;
    sort(stalls.begin(), stalls.end());  // must sort first!

    // Binary search on the answer: what's the maximum possible minimum distance?
    int lo = 1, hi = stalls.back() - stalls.front();
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) {
            answer = mid;    // mid works, try larger
            lo = mid + 1;
        } else {
            hi = mid - 1;    // mid doesn't work, try smaller
        }
    }

    cout << answer << "\n";
    return 0;
}

Trace for stalls = [1, 2, 4, 8, 9], C = 3:

Sorted: [1, 2, 4, 8, 9]
lo=1, hi=8

mid=4: canPlace(4)?
  Place cow at 1. Next stall ≥ 1+4=5: that's 8. Place at 8.
  Next stall ≥ 8+4=12: none. Total placed=2 < 3. Return false.
  → hi = 3

mid=2: canPlace(2)?
  Place cow at 1. Next stall ≥ 3: that's 4. Place at 4.
  Next stall ≥ 6: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=2, lo=3

mid=3: canPlace(3)?
  Place cow at 1. Next ≥ 4: that's 4. Place at 4.
  Next ≥ 7: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=3, lo=4

lo=4 > hi=3: done. Answer = 3

Another Classic: Minimum Time to Complete Tasks (Rope Cutting)

Problem: Given N ropes of lengths L[i], cut K ropes of equal length. What's the maximum length you can cut each piece to?

📝 Code Snippet: The following is a code fragment — for a complete runnable program structure, refer to the Aggressive Cows example above.

// 代码片段 — 完整程序请参考 Aggressive Cows 示例
// Can we get K pieces of length >= len from the ropes?
bool canCut(vector<int> &ropes, long long len, int K) {
    long long count = 0;
    for (int r : ropes) count += r / len;  // pieces from each rope
    return count >= K;
}

// Binary search: maximize len such that canCut(len) is true
long long lo = 1, hi = *max_element(ropes.begin(), ropes.end());
long long answer = 0;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canCut(ropes, mid, K)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}

Template for Binary Search on Answer:

// Generic template — adapt lo, hi, and check() for your problem
long long lo = min_possible_answer;
long long hi = max_possible_answer;
long long answer = lo;  // or -1 if no valid answer exists

while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) {       // mid is feasible
        answer = mid;       // save it
        lo = mid + 1;       // try to do better (or worse, depending on problem)
    } else {
        hi = mid - 1;       // mid not feasible, go lower
    }
}

🏆 USACO Tip: Whenever a USACO problem asks "find the maximum X such that [some condition]" or "find the minimum X such that [some condition]," consider binary search on the answer. This technique solves USACO Silver problems frequently.

3.3.6 Coordinate Compression

Sometimes values are large (up to 10^9), but there are few distinct values. Coordinate compression maps them to small indices (0, 1, 2, ...).

// Solution: Coordinate Compression — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> A = {100, 500, 200, 100, 700, 200};

    // Step 1: Get sorted unique values
    vector<int> sorted_unique = A;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                        sorted_unique.end());
    // sorted_unique = {100, 200, 500, 700}

    // Step 2: Map each original value to its compressed index
    vector<int> compressed(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        compressed[i] = lower_bound(sorted_unique.begin(), sorted_unique.end(), A[i])
                        - sorted_unique.begin();
        // 100→0, 200→1, 500→2, 700→3
    }

    for (int x : compressed) cout << x << " ";
    cout << "\n";  // 0 2 1 0 3 1

    return 0;
}

3.3.7 Advanced Binary Search on Answer — Three Examples

Example 1: Minimum Time to Finish Tasks (Parametric Search)

Problem: N workers, M tasks with effort[i]. Assign tasks to workers (each worker gets contiguous tasks). Minimize the maximum time any worker spends (minimize the bottleneck).

This is the "Painter's Partition" problem. Binary search on the answer (max time T), check if T is achievable.

📝 Template Switch Notice: This example uses while (lo < hi) with hi = mid — different from the while (lo <= hi) template in Section 3.3.5. We switch here because we are minimizing the answer: when canFinish(mid) is true, mid itself is a candidate, so we set hi = mid (not hi = mid - 1) to avoid skipping it. When the loop ends, lo == hi is the answer directly — no need for a separate answer variable. See FAQ Q2 for a detailed comparison of the two templates.

// Check: can we distribute tasks among K workers so max work <= T?
bool canFinish(vector<int>& tasks, int K, long long T) {
    int workers = 1;
    long long current = 0;
    for (int t : tasks) {
        if (t > T) return false;  // single task exceeds T — impossible
        if (current + t > T) {
            workers++;             // start new worker
            current = t;
            if (workers > K) return false;
        } else {
            current += t;
        }
    }
    return true;
}

// Binary search on T — using "lo < hi" template (minimizing the answer)
long long lo = *max_element(tasks.begin(), tasks.end());  // minimum possible T
long long hi = accumulate(tasks.begin(), tasks.end(), 0LL);  // maximum T (1 worker)

while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canFinish(tasks, K, mid)) hi = mid;  // mid works, try smaller
    else lo = mid + 1;                        // mid doesn't work, need larger
}
cout << lo << "\n";  // minimum possible maximum time (lo == hi when loop ends)

📝 Note: Here we binary search for the minimum feasible T, so we use hi = mid when feasible (not answer = mid; lo = mid+1). The two templates are mirror images.

Example 2: Kth Smallest in Multiplication Table

Problem: N×M multiplication table. Find the Kth smallest value.

The table has values i*j for 1≤i≤N, 1≤j≤M. Binary search on the answer X: count how many values are ≤ X.

// Count values <= X in N×M multiplication table
long long countLE(long long X, int N, int M) {
    long long count = 0;
    for (int i = 1; i <= N; i++) {
        count += min((long long)M, X / i);
        // Row i has values i, 2i, ..., Mi
        // Count of values <= X in row i: min(M, floor(X/i))
    }
    return count;
}

// Binary search for Kth smallest
long long lo = 1, hi = (long long)N * M;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (countLE(mid, N, M) >= K) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Complexity: O(N log(NM)) — O(N) per check, O(log(NM)) iterations.

Example 3: USACO-Style Cable Length (Agri-Net inspired)

Problem: Given N farm locations, connect them all with cables. The cables must be at most length L. Find the maximum L such that you can form a spanning tree with all edges ≤ L.

// Binary search on maximum cable length L
// Check: does a spanning tree exist using only edges of length <= L?
// (This reduces to: is the graph connected when restricted to edges <= L?)
bool canConnect(vector<tuple<int,int,int>>& edges, int n, int L) {
    DSU dsu(n);
    for (auto [w, u, v] : edges) {
        if (w <= L) dsu.unite(u, v);
    }
    return dsu.components == 1;  // all nodes connected
}

3.3.8 lower_bound / upper_bound Complete Cheat Sheet

// 注意：以下代码假设已定义：#define all(v) (v).begin(), (v).end()
// 示例中 all 即 v.begin(), v.end()
vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};
//                0  1  2  3  4  5  6   7

// ── lower_bound: first position >= x ──
lower_bound(all(v), 3)  → index 1  (first 3)
lower_bound(all(v), 4)  → index 3  (first element >= 4, which is 5)
lower_bound(all(v), 12) → index 8  (past-end: no element ≥ 12 exists in the array)

// ── upper_bound: first position > x ──
upper_bound(all(v), 3)  → index 3  (first element after all 3s)
upper_bound(all(v), 4)  → index 3  (same as above: no 4s)
upper_bound(all(v), 11) → index 8  (past-end)

// ── Derived operations ──
// Count occurrences of x:
// upper_bound(all(v),3) - lower_bound(all(v),3) = 3 - 1 = 2 ✓
int cnt = upper_bound(all(v), 3) - lower_bound(all(v), 3);  // cnt = 2

// Does x exist?
binary_search(all(v), x)  // O(log N), returns bool

// Largest value <= x (floor):
auto it = upper_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);  // *--it

// Smallest value >= x (ceil):
auto it = lower_bound(all(v), x);
if (it != v.end()) cout << *it;

// Largest value < x (strict floor):
auto it = lower_bound(all(v), x);
if (it != v.begin()) cout << *prev(it);

// Count elements < x:
lower_bound(all(v), x) - v.begin()

// Count elements <= x:
upper_bound(all(v), x) - v.begin()

// Count elements in range [a, b]:
upper_bound(all(v), b) - lower_bound(all(v), a)

3.3.9 Custom Predicate Binary Search

For non-standard sorted structures or custom criteria:

// Binary search with custom predicate
// Find first index i where pred(i) is true, in range [lo, hi]
// Assumption: pred is monotone: false...false, true...true

int lo = 0, hi = n - 1, answer = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (/* some condition on mid */) {
        answer = mid;
        hi = mid - 1;  // look for smaller index
    } else {
        lo = mid + 1;
    }
}

// Example: first index where arr[i] - arr[0] >= D
// (For a sorted array, arr[i] - arr[0] is monotonically non-decreasing,
//  so this predicate is monotone: false...false, true...true)
// ⚠️ Key requirement: the predicate MUST be monotone for binary search to work!
{
    int lo = 0, hi = n - 1, firstFar = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - arr[0] >= D) {  // monotone: once true, stays true for all larger indices
            firstFar = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    // firstFar is the answer
}

// Floating point binary search (epsilon-based)
double lo_f = 0.0, hi_f = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100 iterations → error < 1e-30
    double mid = (lo_f + hi_f) / 2;
    if (check(mid)) hi_f = mid;
    else lo_f = mid;
}
// Answer: lo_f (or hi_f, they converge to same value)

🏆 USACO Pro Tip: "Binary search on answer" is one of the most common Silver techniques. When you see "maximize/minimize X subject to [constraint]," ask yourself: Is the feasibility function monotone? If yes, binary search.

3.3.10 Ternary Search — Finding the Peak of a Unimodal Function 🔮 Advanced / Gold+

⚠️ Scope Note: Ternary search is rarely required in USACO Silver. It appears occasionally in Gold/Platinum problems involving geometric optimization or parametric search. Treat this section as supplementary knowledge — understand the concept, but don't prioritize it over mastering binary search.

Binary search requires a monotone predicate (false→true boundary). For unimodal functions (increases then decreases), use ternary search to find the maximum.

💡 When to use: A function f is unimodal on [lo, hi] if it first strictly increases then strictly decreases (or is always one direction). Ternary search finds the maximum point in O(log((hi-lo)/eps)) evaluations.

USACO appearances: Ternary search rarely appears at Silver level. At Gold/Platinum level, it occasionally appears in problems involving geometric optimization (e.g., "find the optimal point on a line to minimize the sum of distances") or parametric search over a continuous unimodal function.

// Ternary search: find maximum of unimodal function f on [lo, hi]
// Prerequisite: f increases then decreases (unimodal)
// Time: O(log((hi-lo)/eps)) for continuous, or O(log N) for integers

// f must be declared/defined before calling this
double ternarySearch(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // maximum is in [m1, hi]
        else hi = m2;                 // maximum is in [lo, m2]
    }
    return (lo + hi) / 2;  // Maximum point (lo ≈ hi after convergence)
}

// Integer ternary search (when f is defined on integers):
int ternarySearchInt(int lo, int hi) {
    // 使用 > 2 而非 >= 2：保留至少 3 个候选值再暴力枚举。
    // 当范围缩至 2 个元素时，m1 == m2（因为 (hi-lo)/3 == 0），
    // 会导致死循环。用 > 2 可确保安全退出并正确处理边界。
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // Check remaining candidates [lo, hi] (at most 3 elements)
    int best = lo;
    for (int x = lo + 1; x <= hi; x++)
        if (f(x) > f(best)) best = x;
    return best;
}

Contrast with binary search:

⚠️ Note: Ternary search on integers requires care — use while (hi - lo > 2) to avoid infinite loops when the range shrinks to 2 or 3 elements, then brute-force the remaining candidates.

⚠️ Common Mistakes in Chapter 3.3

1. Sorting with wrong comparator: Your lambda must return true if a should come BEFORE b. If it returns true for a == b, you get undefined behavior (strict weak ordering violation).
2. Binary search on unsorted array: lower_bound and upper_bound assume sorted order. On unsorted data, results are meaningless.
3. Off-by-one in binary search: lo <= hi vs lo < hi matters. When in doubt, test your binary search on a 1-element and 2-element array.
4. Wrong answer range in "binary search on answer": If the answer could be 0, set lo = 0, not lo = 1. If it could be very large, make sure hi is large enough (use long long if necessary).
5. Integer overflow in mid computation: Always write mid = lo + (hi - lo) / 2, never (lo + hi) / 2.

Chapter Summary

📌 Key Takeaways

🧩 Binary Search Template Quick Reference

❓ FAQ

Q1: Is sort's time complexity O(N log N) or O(N²)?

A: C++'s std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort), guaranteeing O(N log N) worst case. No need to worry about degrading to O(N²). But note: if your custom comparator doesn't satisfy strict weak ordering, behavior is undefined (may infinite loop or crash).

Q2: What's the difference between lo <= hi and lo < hi in binary search?

A: The two styles correspond to different templates:

• while (lo <= hi): when search ends, lo > hi, answer is stored in answer variable. Good for "find target value" or "maximize value satisfying condition".
• while (lo < hi): when search ends, lo == hi, answer is lo. Good for "minimize value satisfying condition". Both can solve all problems; the key is pairing with the correct update rule. Beginners should pick one style and stick with it.

Q3: What problems is "binary search on answer" applicable to? How to identify them?

A: Three signals: ① The problem asks "the maximum/minimum X such that..."; ② There exists a decision function check(X) that can determine feasibility in polynomial time; ③ The decision function is monotone (X feasible → X-1 also feasible, or vice versa). If all three hold, binary search on answer applies.

Q4: What is coordinate compression actually useful for?

A: When the value range is large (e.g., 10^9) but the number of distinct values is small (e.g., 10^5), coordinate compression maps large values to small indices 0~N-1. This lets you use arrays instead of maps (faster), or perform prefix sums/BIT operations over the value domain. Frequently needed in USACO Silver.

Q5: Why can't the sort comparator use <=?

A: C++ sorting requires the comparator to satisfy strict weak ordering: when a == b, comp(a,b) must return false. <= returns true when a==b, violating this rule. The result is undefined behavior — may infinite loop, crash, or produce incorrect ordering.

🔗 Connections to Later Chapters

• Chapter 3.4 (Two Pointers): two-pointer techniques are often used after sorting — sort first O(N log N), then two pointers O(N)
• Chapter 3.2 (Prefix Sums): prefix sum arrays are naturally ordered, enabling binary search on them (e.g., find first prefix sum ≥ target)
• Chapters 4.1 & 5.4 (Greedy + Shortest Paths): Dijkstra internally uses a priority queue + greedy strategy, fundamentally related to sorting
• Chapter 6.2 (DP): LIS (Longest Increasing Subsequence) can be optimized to O(N log N) using binary search
• "Binary search on answer" is one of the most core techniques in USACO Silver, also frequently combined in Chapter 4.1 (Greedy)

Practice Problems

Problem 3.3.1 — Closest Pair 🟢 Easy Read N integers. Find the pair with the minimum difference.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); for (int& x : a) cin >> x;
    sort(a.begin(), a.end());
    int best = INT_MAX;
    for (int i = 1; i < n; i++)
        best = min(best, a[i] - a[i-1]);
    cout << best << "\n";
}

Problem 3.3.2 — Room Allocation 🟡 Medium N events with start/end times. What is the maximum number of events overlapping at any moment?

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<pair<int,int>> evs;  // (time, delta)
    for (int i = 0; i < n; i++) {
        int s, e; cin >> s >> e;
        evs.push_back({s, +1});
        evs.push_back({e, -1});
    }
    // End-before-start tie-break: when equal time,
    // process ends first (delta=-1) so "touching" intervals don't overlap.
    sort(evs.begin(), evs.end(),
         [](auto& a, auto& b){ return a.first != b.first ? a.first < b.first : a.second < b.second; });
    int cur = 0, best = 0;
    for (auto& [t, d] : evs) { cur += d; best = max(best, cur); }
    cout << best << "\n";
}

Events: (1,+1), (2,+1), (3,+1), (4,-1), (5,-1), (6,-1)
Sweep:   1       2       3       2       1       0
Max: 3 (at time 3, all three intervals active)

Problem 3.3.3 — Kth Smallest 🟡 Medium Find K-th smallest element in array.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n); for (int& x : a) cin >> x;
    // nth_element partitions so that a[k-1] is in correct sorted position
    nth_element(a.begin(), a.begin() + (k-1), a.end());
    cout << a[k-1] << "\n";
}

int lo = *min_element(a.begin(), a.end());
int hi = *max_element(a.begin(), a.end());
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    int cnt = count_if(a.begin(), a.end(), [&](int x){ return x <= mid; });
    if (cnt >= k) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Problem 3.3.4 — Aggressive Cows 🔴 Hard N stalls at positions p[1..N]. Place C cows to maximize the minimum pairwise distance.

#include <bits/stdc++.h>
using namespace std;
int N, C;
vector<int> p;

bool canPlace(int D) {
    int placed = 1, last = p[0];
    for (int i = 1; i < N; i++) {
        if (p[i] - last >= D) { placed++; last = p[i]; }
        if (placed >= C) return true;
    }
    return false;
}

int main() {
    cin >> N >> C;
    p.resize(N); for (int& x : p) cin >> x;
    sort(p.begin(), p.end());

    int lo = 1, hi = p.back() - p.front(), ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) { ans = mid; lo = mid + 1; }  // feasible, try larger
        else hi = mid - 1;
    }
    cout << ans << "\n";
}

Problem 3.3.5 — Painter's Partition 🔴 Hard N boards with widths. K painters, each paints 1 unit time per unit width. Assign contiguous boards to minimize total painting time.

#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<long long> W;

bool canFinish(long long T) {
    int painters = 1;
    long long cur = 0;
    for (long long w : W) {
        if (w > T) return false;  // single board exceeds budget
        if (cur + w > T) { painters++; cur = w; }
        else cur += w;
    }
    return painters <= K;
}

int main() {
    cin >> N >> K;
    W.resize(N); for (long long& x : W) cin >> x;
    long long lo = *max_element(W.begin(), W.end());  // lower bound: largest board
    long long hi = accumulate(W.begin(), W.end(), 0LL);  // upper bound: total sum
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
}

⚠️ Common Mistakes in Sorting & Searching

🏆 Challenge Problem: USACO 2016 February Silver: Fencing the Cows Fence all N points in a convex region using minimum fencing. This is the Convex Hull problem — look up the Graham scan or Jarvis march algorithms. While this is a Gold-level topic, thinking about it now will prime your intuition.