Sort then search

Why this matters

Many coding questions ask about pairs of values. Does a list contain a repeat? Which two numbers are closest? Which two numbers add up to a target? The direct way is to check every pair. For a list of n values there are n times n minus 1, divided by 2, pairs to check. For 1,000 values that is 499,500 pairs. For 100,000 values it is about five billion. Such a program is correct but too slow.

A better method is to sort the list once, and then answer the question by looking only at nearby values. Sorting costs about n times the logarithm of n steps. After that, the question takes one scan through the list or a short search for each value. This lesson shows the three tools that do the work: a scan of neighbours, binary search and two pointers. The sorting itself was covered earlier in this module, and the comparator rules are in the lesson on bad comparator bugs, so this lesson takes a sorted list as its starting point.

Every program in this lesson was compiled with g++ -std=c++20 -Wall -Wextra on g++ 15.2. The outputs are copied from the real runs.

The idea: sorting moves close values next to each other

Start with a list of five numbers: 8 3 6 3 9. Two of the values are 3, but they sit at positions 1 and 3, with a different value between them. To find that repeat, you would have to compare the first 3 with every other value to see if it matches.

Now sort the same list. It becomes 3 3 6 8 9. The two 3 values are side by side. To find a repeat, you only need to compare each value with the value before it. Sorting did the hard work of putting the matches together.

The same idea works for closeness. In a sorted list, the two values that are closest to each other must sit next to each other. If the closest pair were separated by a third value, that third value would be even closer to one of them, so it would be a closer pair instead. That fact is what makes the scan in the next example correct.

Example 1: does the list contain a repeat?

Here is the first program. It takes a list and answers true if any value appears more than once.

#include <algorithm>
#include <iostream>
#include <vector>
 
// Returns true if any value appears more than once. Sorts a copy first.
bool has_duplicate(std::vector<int> v) {
    std::ranges::sort(v);
    for (std::size_t i = 1; i < v.size(); ++i) {
        if (v[i] == v[i - 1]) return true;
    }
    return false;
}
 
int main() {
    std::vector<int> a = {8, 3, 6, 1, 9};
    std::vector<int> b = {8, 3, 6, 3, 9};
    std::cout << std::boolalpha;
    std::cout << "a has duplicate: " << has_duplicate(a) << '\n';
    std::cout << "b has duplicate: " << has_duplicate(b) << '\n';
    std::cout << "original b after call: ";
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';
}

The output is:

a has duplicate: false
b has duplicate: true
original b after call: 8 3 6 3 9 

Look at the function header first. It takes std::vector<int> v without the &, so the function gets its own copy of the list. The sort changes only that copy. The last line of the output shows that the list b in main is still in its original order, 8 3 6 3 9. The copy is a choice. If you wrote std::vector<int>& v, the caller's list would be sorted as well. Sometimes that is what you want. Here it would be a surprise to the caller, so the copy is the safer choice.

The loop starts at i = 1 and compares v[i] with v[i - 1], the value before it. For b, the sorted copy is 3 3 6 8 9. At i = 1, the two values are both 3, so the function returns true at once.

A shorter version with a standard function

The standard library has a function that does this loop for you. std::ranges::adjacent_find returns an iterator to the first place where two neighbouring values are equal, or the end of the list if there is none. The example below runs it on the same list before and after sorting:

#include <algorithm>
#include <iostream>
#include <vector>
 
bool adjacent_equal(const std::vector<int>& v) {
    return std::ranges::adjacent_find(v) != v.end();
}
 
int main() {
    std::vector<int> v = {3, 1, 3};
    std::cout << std::boolalpha;
    std::cout << "unsorted, adjacent check: " << adjacent_equal(v) << '\n';
    std::ranges::sort(v);
    std::cout << "sorted, adjacent check:   " << adjacent_equal(v) << '\n';
    auto it = std::ranges::adjacent_find(v);
    std::cout << "first equal pair starts at index " << (it - v.begin()) << " value " << *it << '\n';
}

The output is:

unsorted, adjacent check: false
sorted, adjacent check:   true
first equal pair starts at index 1 value 3

The first line shows the mistake this lesson is about. The list 3 1 3 has a repeat, but the two 3 values are not next to each other, so the neighbour check says false. After sorting, the list is 1 3 3, and the check finds the repeat. The sort is required, not optional.

What it costs

The sort takes about n times the logarithm of n steps. The scan takes n steps. For 1,000 values, the sort takes roughly 10,000 steps and the scan about 1,000. The pair check took 499,500 steps. The gap grows quickly as the list gets longer. This lesson does not measure time. The timing lesson in this module counts comparisons directly.

Example 2: the closest pair of values

Suppose you have a list of numbers and want the two numbers with the smallest difference between them. Here is a program that does it:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {8, 1, 14, 6, 10, 3};
    std::ranges::sort(v);
    std::cout << "sorted: ";
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
 
    int best_gap = v[1] - v[0];
    std::size_t best = 0;
    for (std::size_t i = 1; i + 1 < v.size(); ++i) {
        int gap = v[i + 1] - v[i];
        if (gap < best_gap) {
            best_gap = gap;
            best = i;
        }
    }
    std::cout << "closest pair: " << v[best] << " and " << v[best + 1]
              << " (gap " << best_gap << ")\n";
}

The output is:

sorted: 1 3 6 8 10 14 
closest pair: 1 and 3 (gap 2)

After sorting, the list is 1 3 6 8 10 14. The gaps between neighbours are 2, 3, 2, 2 and 4. The program starts by treating the first gap as the best, then checks every other neighbour pair. It replaces the best gap only when the new gap is strictly smaller, so the first pair with the smallest gap wins. Three pairs have a gap of 2: 1 and 3, 6 and 8, and 8 and 10. The program reports the first one.

The loop checks neighbours only, and that is enough. The reason is the rule from the idea section. If the closest pair were x and y, with a value z between them, then z is at most as far from x as y is, and at most as far from y as x is. So the pair x and z, or the pair z and y, is at least as close. A neighbour pair is always at least as close as any other pair, so the scan finds the answer.

Example: the nearest store to each house

The second example is harder, because the question is asked many times. A town has a list of store positions, and each house wants the distance to its nearest store. Scanning all stores for each house takes time that grows with both lists. A better way is to sort the stores once, then use binary search to find the nearest one for each house.

Binary search is a method for finding a value in a sorted list. It checks the middle item, decides which half the answer is in, throws the other half away and repeats. Each step halves the search, so a list of a million values needs about 20 steps. The standard function std::ranges::lower_bound uses binary search. It returns an iterator to the first value that is not less than the target. If every value is less than the target, it returns the end of the list.

#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>
 
// For each house, the distance to the nearest store. stores must be sorted.
int nearest_distance(const std::vector<int>& stores, int house) {
    int best = INT_MAX;
    auto it = std::ranges::lower_bound(stores, house);  // first store at or past the house
    if (it != stores.end()) best = std::min(best, std::abs(*it - house));
    if (it != stores.begin()) best = std::min(best, std::abs(*std::prev(it) - house));
    return best;
}
 
int main() {
    std::vector<int> stores = {40, 10, 75, 22};
    std::vector<int> houses = {12, 30, 60, 90, 1};
    std::ranges::sort(stores);
    for (int h : houses) {
        std::cout << "house at " << h << ": nearest store " << nearest_distance(stores, h) << " away\n";
    }
}

The output is:

house at 12: nearest store 2 away
house at 30: nearest store 8 away
house at 60: nearest store 15 away
house at 90: nearest store 15 away
house at 1: nearest store 9 away

Take the house at 12 as a worked example. The sorted stores are 10 22 40 75. lower_bound returns the iterator to 22, the first store at or past position 12. The nearest store is either that one or the store just before it. The distance to 22 is 10. The distance to 10, the store before it, is 2. The answer is 2.

The two if lines handle the edges. If the house is past every store, lower_bound returns the end, and only the store before it is checked. If the house is before every store, lower_bound returns the first store, and there is no store before it, so only the first store is checked. Without these checks, the program would read outside the list.

Each house now costs about the logarithm of the number of stores, plus the one sort. The first house checks two stores, and the search for the other houses follows the same pattern.

Example 3: two pointers for a pair with a given sum

Some questions need the pair that adds up to a target. Sorting makes this fast with a method called two pointers. A pointer here is just an index that marks a position in the list. Put one index at the start of the sorted list, and one at the end. Compare the sum of the two values with the target.

• If the sum is too small, move the left index one step to the right, to a bigger value.
• If the sum is too big, move the right index one step to the left, to a smaller value.
• If the sum matches, print the pair and move both indexes inward.

Here is the program:

#include <algorithm>
#include <iostream>
#include <vector>
 
// Print every pair of values that adds up to target. Works on sorted input.
void print_pairs(const std::vector<int>& sorted, int target) {
    std::size_t lo = 0;
    std::size_t hi = sorted.size() - 1;
    while (lo < hi) {
        int sum = sorted[lo] + sorted[hi];
        if (sum == target) {
            std::cout << sorted[lo] << " + " << sorted[hi] << " = " << target << '\n';
            ++lo;
            --hi;
        } else if (sum < target) {
            ++lo;
        } else {
            --hi;
        }
    }
}
 
int main() {
    std::vector<int> v = {11, 3, 8, 1, 6, 4};
    std::ranges::sort(v);
    print_pairs(v, 10);
}

The output is:

4 + 6 = 10

Trace the sorted list 1 3 4 6 8 11 with target 10. The indexes are lo = 0 and hi = 5.

After the match, lo is 3 and hi is 2, so the loop ends. The output has one pair.

Why is it safe to move an index? Take step 1. The sum of 1 and 11 is too big. The value 11 is the largest left in the list, so every partner for it gives a sum that is too big. Dropping it cannot lose a valid pair. The same reasoning applies when the sum is too small and lo moves: the value at lo is the smallest one left, so even its largest partner, the value at hi, gives a sum that is too small.

This method runs in one pass through the list, so the cost is about n steps, after the sort. The program needs the list to be sorted, because the decision to move lo or hi depends on the values being in order.

Harder: counting the pairs

Sometimes you need a count, not a list. Here is a version that counts the pairs whose sum is at most a limit. It needs care, because one left value can pair with many right values at once.

#include <algorithm>
#include <iostream>
#include <vector>
 
// Count pairs (i, j) with i < j and sorted[i] + sorted[j] <= limit.
long long count_pairs_at_most(const std::vector<int>& sorted, int limit) {
    long long count = 0;
    std::size_t lo = 0;
    std::size_t hi = sorted.size();
    while (lo + 1 < hi) {
        if (sorted[lo] + sorted[hi - 1] <= limit) {
            // sorted[lo] pairs with every value from lo+1 up to hi-1.
            count += static_cast<long long>(hi - 1 - lo);
            ++lo;
        } else {
            --hi;
        }
    }
    return count;
}
 
int main() {
    std::vector<int> v = {4, 1, 7, 3, 9};
    std::ranges::sort(v);
    std::cout << "pairs with sum <= 8: " << count_pairs_at_most(v, 8) << '\n';
}

The output is:

pairs with sum <= 8: 4

The list is 1 3 4 7 9, and the four pairs are 1 + 3, 1 + 4, 1 + 7 and 3 + 4. When the sum of sorted[lo] and sorted[hi - 1] is within the limit, every value between lo and hi - 1 also pairs with sorted[lo] within the limit, because those values are smaller. So the program adds all of them at once and moves lo on. The count is the number of values from lo + 1 to hi - 1, which is hi - 1 - lo.

Example 4: the closest value to a target

The last example combines binary search with a check on both sides. Given a sorted list and a target that may not be in it, find the value closest to the target. If the target is in the list, that value is the answer. If not, the answer is either the value just below or the value just above.

#include <algorithm>
#include <iostream>
#include <vector>
 
// Index of the value in sorted v that is closest to target.
std::size_t closest_index(const std::vector<int>& v, int target) {
    auto it = std::ranges::lower_bound(v, target);  // first value >= target
    if (it == v.begin()) return 0;
    if (it == v.end()) return v.size() - 1;
    auto above = static_cast<std::size_t>(it - v.begin());
    auto below = above - 1;
    return (target - v[below] <= v[above] - target) ? below : above;
}
 
int main() {
    std::vector<int> v = {2, 5, 9, 14, 20};
    for (int target : {1, 6, 12, 19, 40}) {
        std::cout << "target " << target << " -> closest " << v[closest_index(v, target)] << '\n';
    }
}

The output is:

target 1 -> closest 2
target 6 -> closest 5
target 12 -> closest 14
target 19 -> closest 20
target 40 -> closest 20

The function handles three cases. A target at or below the first value returns the first value. A target above the last value returns the last value. Any other target has a value below it and a value at or above it, and the function compares the two distances. When the distances are equal, the code picks the lower value, because the <= in the return line prefers below. The output for target 12 shows the rule in use: 14 is 2 away and 9 is 3 away, so 14 wins.

Common mistakes

Forgetting to sort first

Every method in this lesson depends on sorted input. Without the sort, the answers are not just slower to find. They are wrong, and often without any message. The adjacent check in Example 1 gave false for 3 1 3, because the repeat was not next to its match. The same kind of mistake with std::lower_bound gives a wrong index without any warning:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {4, 9, 1, 7};
    auto it = std::lower_bound(v.begin(), v.end(), 7);
    std::cout << "found index " << (it - v.begin()) << '\n';
}

The output is:

found index 3

The first value that is 7 or more is 9, at index 1. The program reports index 3, because lower_bound assumes the list is sorted, and it followed a path that was never valid for this list. The result looks plausible, which is why this bug is hard to spot. If you compile the program with -D_GLIBCXX_DEBUG, the standard library checks the precondition and stops with this message, shown here with the line break joined:

Error: elements in iterator range [first, last) are not partitioned by the value __val.

The message is a good hint. "Partitioned" is the formal name for "sorted with respect to this value", and the message names the requirement the list broke.

Reading the end of the list

lower_bound returns the end of the list when no value is large enough. The end is a position one past the last value, and it holds no value. Reading it is undefined behaviour. This program has that bug:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {1, 3, 5};
    auto it = std::ranges::lower_bound(v, 9);  // nothing is >= 9, so it == end()
    std::cout << *it << '\n';
}

Without any extra flags, the program still compiles and prints a number that is not in the list. On the build used here, that number was 0, which is whatever the memory held. Compiled with -D_GLIBCXX_DEBUG, the program stops with:

Error: attempt to dereference a past-the-end iterator.

Compiled with -fsanitize=address, the address sanitizer reports the same mistake as a memory error. The first line of its report is:

ERROR: AddressSanitizer: heap-buffer-overflow on address 0x... READ of size 4

The fix is to test the iterator first: if (it != v.end()) std::cout << *it << '\n';.

Taking an empty list

The two-pointer program in Example 3 starts with sorted.size() - 1. For an empty list, size() is 0, and 0 - 1 wraps around to a very large number, because size() returns an unsigned type. The loop then reads positions that do not exist. This call crashes on the compiler used for this lesson:

#include <algorithm>
#include <iostream>
#include <vector>
 
void print_pairs(const std::vector<int>& sorted, int target) {
    std::size_t lo = 0;
    std::size_t hi = sorted.size() - 1;
    while (lo < hi) {
        int sum = sorted[lo] + sorted[hi];
        if (sum == target) {
            std::cout << sorted[lo] << " + " << sorted[hi] << '\n';
            ++lo;
            --hi;
        } else if (sum < target) {
            ++lo;
        } else {
            --hi;
        }
    }
}
 
int main() {
    std::vector<int> empty;
    print_pairs(empty, 10);
}

The output is:

/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The program stops with exit code 134, which is the code for a program that calls abort. Ubuntu's g++ turns this check on in the default build (no -O flag). With -O2 the same program crashes with exit code 139, a segmentation fault, and prints no message. The fix is to return early when the list is empty. Put if (sorted.empty()) return; at the top of the function.

Using binary_search when you need a position

std::ranges::binary_search answers only yes or no. It returns a bool, and it does not say where the value is. Here is a program that prints that result:

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v = {1, 3, 5, 7, 9};
    std::ranges::sort(v);
    std::cout << "has 5: " << std::ranges::binary_search(v, 5) << '\n';
}

The output is:

has 5: 1

The 1 is true printed as a number, because this program does not set std::boolalpha. If you need the position, use lower_bound and check the value it points to: it != v.end() && *it == 5.

Practice

Exercise 1. Write a function that counts the distinct values in a sorted list. Test it on {7, 2, 7, 9, 2, 2, 5} after sorting.

Show the answer

The function counts the first value, then adds one each time a value differs from the one before it. The code is in the example below, and the output is distinct: 4, because the distinct values are 2, 5, 7 and 9.

#include <algorithm>
#include <iostream>
#include <vector>
 
std::size_t count_distinct(const std::vector<int>& sorted) {
    if (sorted.empty()) return 0;
    std::size_t count = 1;
    for (std::size_t i = 1; i < sorted.size(); ++i) {
        if (sorted[i] != sorted[i - 1]) ++count;
    }
    return count;
}
 
int main() {
    std::vector<int> v = {7, 2, 7, 9, 2, 2, 5};
    std::ranges::sort(v);
    std::cout << "distinct: " << count_distinct(v) << '\n';
}

Exercise 2. Given two lists a = {1, 6, 20} and b = {3, 9, 14, 30}, find the smallest difference between a value in a and a value in b. Sort b once, then search it for each value of a.

Show the answer

For each value in a, use lower_bound on b and check the value at that position and the one before it. The answer is 2, from the pair 1 and 3. The code below prints it:

#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
 
int min_cross_gap(const std::vector<int>& a, const std::vector<int>& b) {
    int best = INT_MAX;
    for (int x : a) {
        auto it = std::ranges::lower_bound(b, x);
        if (it != b.end()) best = std::min(best, std::abs(*it - x));
        if (it != b.begin()) best = std::min(best, std::abs(*std::prev(it) - x));
    }
    return best;
}
 
int main() {
    std::vector<int> a = {1, 6, 20};
    std::vector<int> b = {3, 9, 14, 30};
    std::cout << "smallest gap: " << min_cross_gap(a, b) << '\n';
}

This version assumes b is already sorted. The output is smallest gap: 2. The list a does not need to be sorted, because each of its values is searched on its own.

Exercise 3. Using the sorted list 1 3 4 7 9 and the limit 8, count the pairs whose sum is at most 8. Explain why the answer is 4 before you run the code.

Show the answer

The pairs are 1 + 3 = 4, 1 + 4 = 5, 1 + 7 = 8 and 3 + 4 = 7. The pairs with 9 are all too big, because 1 + 9 = 10. So the count is 4. The program in the lesson prints pairs with sum <= 8: 4.

Exercise 4. The two-pointer function in Example 3 crashes on an empty list. Explain the cause in one sentence, then write the fix.

Show the answer

sorted.size() - 1 wraps to a very large number when the list is empty, because size() is unsigned. The fix is to add if (sorted.empty()) return; as the first line of the function. With that line, the call on the empty list prints nothing and exits normally.

Exercise 5. A teammate uses std::ranges::binary_search(v, 5) and then tries to print the index of the 5 from the result. Explain what goes wrong and write the correct lookup.

Show the answer

binary_search returns only true or false, so the result has no index. Use auto it = std::ranges::lower_bound(v, 5); and then check if (it != v.end() && *it == 5). If the check passes, it - v.begin() is the index of the value.

Summary

• Sorting once makes many pair questions cheap: a sort costs about n times the logarithm of n, and each question after it costs about n steps or less.
• In a sorted list, duplicates sit next to each other, and the closest pair is always two neighbours.
• lower_bound finds the first value that is not less than a target, and checking the position before it gives the nearest value on the lower side.
• Two pointers walk inward from both ends. A sum that is too small moves the left index, and a sum that is too big moves the right index.
• All of these methods need sorted input, and the result is wrong without any message if the list is not sorted.
• Check for an empty list and for the end position before reading a value.