C++ Sorting & Searching Algorithms: sort, find, binary_search Guide
Table of Contents
STL Algorithm Philosophy
STL algorithms operate on iterator ranges, not containers directly. They take a [begin, end) pair and process elements without knowing what container holds them. This means the same std::sort works on vectors, arrays, deques, and raw C arrays — anything with random-access iterators.
All sorting and searching algorithms live in <algorithm>. They never allocate memory or change container size — they only rearrange or inspect elements within the given range. If you need to grow a container during an algorithm, use iterator adapters like std::back_inserter.
std::sort and Variants
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// std::sort — Introsort (quicksort + heapsort + insertion sort)
// O(n log n) average and worst case
// Requires random-access iterators
std::sort(v.begin(), v.end());
// v = {1, 2, 3, 4, 5, 6, 7, 8, 9}
// Sort descending
std::sort(v.begin(), v.end(), std::greater<int>{});
// v = {9, 8, 7, 6, 5, 4, 3, 2, 1}
// Sort with custom comparator
std::vector<std::string> words = {"banana", "apple", "cherry", "date"};
std::sort(words.begin(), words.end(),
[](const std::string& a, const std::string& b) {
return a.size() < b.size(); // sort by length
});
// words = {"date", "apple", "banana", "cherry"}
// std::stable_sort — preserves order of equal elements
// O(n log n) but may use O(n) extra memory
struct Student { std::string name; int grade; };
std::vector<Student> students = {
{"Alice", 90}, {"Bob", 85}, {"Charlie", 90}, {"Diana", 85}
};
std::stable_sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.grade > b.grade;
});
// {Alice:90, Charlie:90, Bob:85, Diana:85}
// Same-grade students keep original order
// std::is_sorted — check if range is sorted
std::vector<int> sorted = {1, 2, 3, 4, 5};
std::cout << std::is_sorted(sorted.begin(), sorted.end()) << "\n"; // 1
// std::is_sorted_until — find where sorting breaks
std::vector<int> partial = {1, 2, 5, 3, 4};
auto until = std::is_sorted_until(partial.begin(), partial.end());
std::cout << "Sorted until index: " << (until - partial.begin()) << "\n"; // 3
}Partial Sorting
When you don’t need the entire range sorted — just the top K elements — partial sorting algorithms are faster:
#include <algorithm>
#include <vector>
std::vector<int> v = {9, 4, 7, 2, 5, 8, 1, 3, 6};
// std::partial_sort — sort first K elements
// O(n log k) — faster than full sort when k << n
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// First 3 elements are sorted: {1, 2, 3, ...rest unsorted...}
// v = {1, 2, 3, 9, 7, 8, 5, 4, 6} (typical)
// Top 3 largest
std::partial_sort(v.begin(), v.begin() + 3, v.end(), std::greater<>{});
// First 3 = {9, 8, 7, ...rest unsorted...}
// std::nth_element — find the Kth element efficiently
// O(n) average — like quickselect
std::vector<int> data = {9, 4, 7, 2, 5, 8, 1, 3, 6};
std::nth_element(data.begin(), data.begin() + 4, data.end());
// data[4] is now 5 (the median-ish value)
// Elements before it are all <= 5
// Elements after it are all >= 5
// But neither side is sorted within itself
// Use case: find median
std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
size_t mid = nums.size() / 2;
std::nth_element(nums.begin(), nums.begin() + mid, nums.end());
int median = nums[mid]; // O(n) instead of O(n log n)
// std::partial_sort_copy — sort into separate output
std::vector<int> source = {5, 2, 8, 1, 9, 3};
std::vector<int> top3(3);
std::partial_sort_copy(source.begin(), source.end(),
top3.begin(), top3.end());
// top3 = {1, 2, 3} — source unchangedSearching Unsorted Data
#include <algorithm>
#include <vector>
#include <string>
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// std::find — linear search O(n)
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) {
std::cout << "Found 8 at index: " << (it - v.begin()) << "\n";
}
// std::find_if — search with predicate
auto even = std::find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
std::cout << "First even: " << *even << "\n"; // 2
// std::find_if_not — first element NOT matching predicate
auto not_small = std::find_if_not(v.begin(), v.end(), [](int x) { return x < 5; });
// std::count / std::count_if
int even_count = std::count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
std::cout << "Even numbers: " << even_count << "\n"; // 4
// std::all_of / std::any_of / std::none_of
bool all_positive = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool has_negative = std::any_of(v.begin(), v.end(), [](int x) { return x < 0; });
bool no_zeros = std::none_of(v.begin(), v.end(), [](int x) { return x == 0; });
// std::search — find subsequence
std::vector<int> haystack = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> needle = {3, 4, 5};
auto sub = std::search(haystack.begin(), haystack.end(),
needle.begin(), needle.end());
if (sub != haystack.end()) {
std::cout << "Subsequence at: " << (sub - haystack.begin()) << "\n"; // 2
}
// std::adjacent_find — find consecutive equal elements
std::vector<int> data = {1, 2, 3, 3, 4, 5};
auto adj = std::adjacent_find(data.begin(), data.end());
if (adj != data.end()) {
std::cout << "Adjacent pair: " << *adj << "\n"; // 3
}Binary Search Algorithms
Binary search algorithms require a sorted range. They run in O(log n):
#include <algorithm>
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// MUST be sorted for binary search!
// std::binary_search — returns bool (exists or not)
bool found = std::binary_search(v.begin(), v.end(), 5); // true
bool not_found = std::binary_search(v.begin(), v.end(), 11); // false
// std::lower_bound — first element >= value
auto lb = std::lower_bound(v.begin(), v.end(), 5);
// points to 5
// std::upper_bound — first element > value
auto ub = std::upper_bound(v.begin(), v.end(), 5);
// points to 6
// Insertion point: lower_bound tells you where to insert to keep sorted
std::vector<int> sorted = {1, 3, 5, 7, 9};
auto pos = std::lower_bound(sorted.begin(), sorted.end(), 4);
sorted.insert(pos, 4); // {1, 3, 4, 5, 7, 9}
// std::equal_range — returns [lower_bound, upper_bound) pair
std::vector<int> data = {1, 2, 2, 2, 3, 4, 5};
auto [lo, hi] = std::equal_range(data.begin(), data.end(), 2);
int count = std::distance(lo, hi); // 3 (three 2s)
std::cout << "2 appears " << count << " times\n";
// Find exact element (lower_bound + check)
auto it = std::lower_bound(v.begin(), v.end(), 7);
if (it != v.end() && *it == 7) {
std::cout << "Found 7 at index: " << (it - v.begin()) << "\n";
}
// Better than binary_search because you get the position, not just boolIn practice, prefer lower_bound over binary_search. binary_search only tells you yes/no. lower_bound gives you the position, and you can check *it == value yourself. It’s more flexible with the same O(log n) cost.
Custom Comparators
#include <algorithm>
#include <vector>
#include <string>
struct Employee {
std::string name;
int salary;
int years;
};
std::vector<Employee> team = {
{"Alice", 120000, 5},
{"Bob", 95000, 3},
{"Charlie", 110000, 7},
{"Diana", 105000, 2}
};
// Sort by salary descending
std::sort(team.begin(), team.end(), [](const Employee& a, const Employee& b) {
return a.salary > b.salary;
});
// Sort by multiple criteria: salary desc, then years asc
std::sort(team.begin(), team.end(), [](const Employee& a, const Employee& b) {
if (a.salary != b.salary) return a.salary > b.salary;
return a.years < b.years;
});
// Binary search with comparator (must match sort order!)
std::sort(team.begin(), team.end(), [](const Employee& a, const Employee& b) {
return a.salary < b.salary;
});
// Find first employee with salary >= 100000
auto it = std::lower_bound(team.begin(), team.end(), 100000,
[](const Employee& emp, int sal) { return emp.salary < sal; });
// Projection-based comparator pattern
auto by_field = [](auto getter) {
return [getter](const auto& a, const auto& b) {
return getter(a) < getter(b);
};
};
std::sort(team.begin(), team.end(), by_field([](const Employee& e) { return e.name; }));Min and Max Algorithms
#include <algorithm>
#include <vector>
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Min/max element — returns iterator
auto min_it = std::min_element(v.begin(), v.end());
auto max_it = std::max_element(v.begin(), v.end());
std::cout << "Min: " << *min_it << " at index " << (min_it - v.begin()) << "\n";
std::cout << "Max: " << *max_it << " at index " << (max_it - v.begin()) << "\n";
// minmax_element — find both in one pass (1.5n comparisons vs 2n)
auto [lo, hi] = std::minmax_element(v.begin(), v.end());
// std::min / std::max / std::minmax — for individual values
int a = std::min(3, 7); // 3
int b = std::max(3, 7); // 7
auto [mn, mx] = std::minmax(3, 7); // {3, 7}
// With initializer list
int smallest = std::min({5, 2, 8, 1, 9}); // 1
// std::clamp (C++17) — restrict to range
int clamped = std::clamp(15, 0, 10); // 10
int clamped2 = std::clamp(-5, 0, 10); // 0
int clamped3 = std::clamp(7, 0, 10); // 7Heap Algorithms
You can build and manipulate heaps directly on a vector without using priority_queue:
#include <algorithm>
#include <vector>
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Build a max-heap — O(n)
std::make_heap(v.begin(), v.end());
// v[0] is now the largest: 9
// Push to heap — O(log n)
v.push_back(10);
std::push_heap(v.begin(), v.end()); // restore heap property
// v[0] is now 10
// Pop from heap — O(log n)
std::pop_heap(v.begin(), v.end()); // moves max to back
int max_val = v.back(); // 10
v.pop_back(); // remove it
// Sort a heap — O(n log n)
std::sort_heap(v.begin(), v.end());
// v is now sorted ascending
// Check if range is a heap
bool is_heap = std::is_heap(v.begin(), v.end());
// Heapsort in one line
std::vector<int> data = {5, 2, 8, 1, 9, 3};
std::make_heap(data.begin(), data.end());
std::sort_heap(data.begin(), data.end());
// data = {1, 2, 3, 5, 8, 9}Merge Algorithms
#include <algorithm>
#include <vector>
// Merge two sorted ranges — O(n + m)
std::vector<int> a = {1, 3, 5, 7};
std::vector<int> b = {2, 4, 6, 8};
std::vector<int> merged(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());
// merged = {1, 2, 3, 4, 5, 6, 7, 8}
// std::inplace_merge — merge two sorted halves of one range
std::vector<int> v = {1, 3, 5, 2, 4, 6};
// sorted sorted
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
// v = {1, 2, 3, 4, 5, 6}
// Useful after sorting two halves independentlyRanges Versions (C++20)
#include <algorithm>
#include <ranges>
#include <vector>
std::vector<int> v = {5, 2, 8, 1, 9, 3};
// Ranges algorithms accept containers directly — no .begin()/.end()
std::ranges::sort(v);
std::ranges::reverse(v);
// Projection — sort by a derived value
struct Person { std::string name; int age; };
std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
// Sort by age using projection (no lambda comparator needed!)
std::ranges::sort(people, {}, &Person::age);
// Equivalent to: sort by person.age ascending
// Sort by name descending
std::ranges::sort(people, std::ranges::greater{}, &Person::name);
// Find with projection
auto it = std::ranges::find(people, "Bob", &Person::name);
// Binary search with projection
std::ranges::sort(people, {}, &Person::age);
bool found = std::ranges::binary_search(people, 30, {}, &Person::age);
// min/max with projection
auto youngest = std::ranges::min(people, {}, &Person::age);
auto oldest = std::ranges::max(people, {}, &Person::age);C++20 ranges projections are a game-changer. Instead of writing [](const Person& a, const Person& b) { return a.age < b.age; }, you write {}, &Person::age. The {} is the default comparator (less), and the projection extracts the field to compare on. Cleaner, shorter, less error-prone.
Common Mistakes
Binary searching unsorted data. binary_search, lower_bound, and upper_bound require sorted ranges. Using them on unsorted data produces wrong results — no error, just silently incorrect.
Mismatched sort and search comparators. If you sort with std::greater (descending), you must also pass std::greater to lower_bound. Using the default less comparator on descending data gives wrong results.
Using std::sort on list. std::sort requires random-access iterators. list provides bidirectional iterators. Use list.sort() instead.
Not checking find return value. std::find returns end() when the element isn’t found. Dereferencing end() is undefined behavior. Always check it != container.end().
Confusing lower_bound and upper_bound. lower_bound returns the first element >= value. upper_bound returns the first element > value. For counting occurrences of a value, use equal_range which returns both.
Summary
std::sort provides O(n log n) general-purpose sorting with Introsort. stable_sort preserves equal-element order. partial_sort and nth_element handle top-K and selection problems faster. Linear search uses find/find_if/count_if. Binary search algorithms (lower_bound, upper_bound, equal_range) provide O(log n) lookup on sorted data. Heap algorithms build and manipulate heaps directly on vectors. C++20 ranges add projections for cleaner comparisons. Always ensure data is sorted before using binary search algorithms. In the next lesson, you’ll explore transform, accumulate, and other data-processing algorithms that round out the STL toolkit.
