Sorting, comparators, and binary search

std::sort, custom orders, lower_bound / upper_bound, and the “binary search on answer” mindset.

std::sort and stability

sort(begin, end) sorts ascending by default for primitives and pair (lexicographic).

Complexity: O(n log n) on average; sort is introspective — good constants in practice.

stable_sort: preserves relative order of equal elements — O(n log² n) worst case extra memory, or O(n log n) if extra memory available. Use when ties must keep input order (e.g. “sort by score, break ties by earlier index” — often easier to sort (score, -index) or use stable_sort).

Example — sort array, then process duplicates together:

vector<int> a(n);
// ... read
sort(a.begin(), a.end());
for (int i = 0; i < n; ) {
    int j = i;
    while (j < n && a[j] == a[i]) j++;
    int len = j - i;  // count of a[i]
    i = j;
}

Example — stable_sort keeps old order among equals:

vector<pair<int,int>> a = {{1,0},{1,1},{2,0}};
stable_sort(a.begin(), a.end(), [](auto& x, auto& y) {
    return x.first < y.first;
});
// both (1,*) keep relative order 0 then 1

Custom comparators

A comparator cmp(a,b) returns true if a should go before b. It must define a strict weak ordering (no contradictions).

Lambda (C++11+):

sort(a.begin(), a.end(), [](const Edge& x, const Edge& y) {
    return x.w < y.w;
});

Classic pitfalls:

Using <= instead of < breaks strict ordering.
Sorting indices: store vector<int> id(n); iota(...); sort(id.begin(), id.end(), [&](int i, int j){ return a[i] < a[j]; });

Example — sort indices by a[i] (do not reorder a):

int n = (int)a.size();
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
    if (a[i] != a[j]) return a[i] < a[j];
    return i < j;  // tie-break for strict weak order
});

Example — struct comparator (Kruskal-style):

struct Edge { int u, v, w; };
bool cmpE(const Edge& A, const Edge& B) {
    return A.w < B.w;
}
vector<Edge> e;
sort(e.begin(), e.end(), cmpE);

Example — sort descending:

sort(a.begin(), a.end(), greater<int>());
// or: sort(..., [](int x, int y){ return x > y; });

lower_bound, upper_bound, equal_range

On sorted ranges:

lower_bound — first position ≥ x (first place you could insert x keeping order).
upper_bound — first position > x.
equal_range — pair of both; count of x is upper - lower.

All run in O(log n) for random-access iterators (e.g. vector).

Pattern: “smallest value ≥ target” → lower_bound. “Strictly greater” → upper_bound.

Example — count occurrences of x in sorted vector:

auto p = equal_range(a.begin(), a.end(), x);
int cnt = int(p.second - p.first);

Example — first element > x:

auto it = upper_bound(a.begin(), a.end(), x);
if (it == a.end()) { /* none */ }
else { int y = *it; }

Example — lower_bound on vector<long long> for “minimum pile ≥ need”:

long long need = ...;
auto it = lower_bound(piles.begin(), piles.end(), need);
if (it == piles.end()) { /* impossible */ }

Binary search on the answer

Many problems ask: “What is the minimum K such that some property holds?” If the property is monotone in K (false…false true…true), binary search the boundary.

You implement check(K) (greedy, simulation, or another DS) and search lo..hi. This is not the same as binary_search on an array — it’s searching the integer answer space.

Invariant style: keep lo always bad and hi always good (or the dual), shrink until hi - lo == 1, then answer is hi. Practice until the +1 / −1 off-by-one issues disappear.

Example — minimal K with check(K) monotone:

auto check = [&](long long K) -> bool {
    // return true if answer <= K works
    return true;  // replace with real test
};
long long lo = 0;    // known bad
long long hi = 1e18; // known good
while (hi - lo > 1) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;
    else lo = mid;
}
cout << hi << "\n";

Example — max K (flip if):

// lo bad, hi good for "at least K"; for "at most K" swap logic
if (check(mid)) lo = mid;
else hi = mid;
// adjust until convergence pattern matches your invariant

Pseudocode: bounds

After sorting a, finding first index with value ≥ x is exactly lower_bound. Use that instead of hand-written binary search when possible — fewer bugs.

1SORT array with optional comparator
2// First position where value >= x:
3L = 0, R = n
4while L < R
5  M = (L + R) / 2
6  if array[M] >= x then R = M else L = M + 1
7return L   // same idea as lower_bound

Complexity

sort: O(n log n). lower_bound / upper_bound: O(log n) per query on a sorted random-access container.

Tip: If you need many order-statistic queries on a changing set, sorting once is not enough — then you move to set, Fenwick/segment tree, or order-statistic tree (policy-based DS outside standard STL).

Complexity Analysis

Time Complexity

O(n log n) sort; O(log n) per bound query

Space Complexity

O(1) extra for sort in practice (implementation-dependent)

Bounds require sorted order; unsorted data gives meaningless positions

Growth Rate Comparison