📦 Phase 4 · STL 🟡 Intermediate MODULE 18

Algorithms — sort, search, binary search

⏱️ 25 min read

📖 Theory + Code

🧩 5 Quiz Questions

🏗️ 1 Challenge

Your progress in Phase 4 — STL80%

🎯 What you'll learn: The <algorithm> header's most-used tools — sort (with custom comparators), find, binary_search, max_element/min_element, and reverse — the functions you'll reach for constantly once you're working with containers.

Section 1

The <algorithm> Header

So far you've learned where to store data (vector, map, stack...). The <algorithm> header gives you ready-made functions for the things you constantly need to do with that data: sorting it, searching through it, finding extremes, reversing it, and dozens more.

Nearly every algorithm in this header follows the same pattern: you pass it a range, described by two iterators — a .begin() and an .end() — telling it exactly where to start and stop working.

💡

Why iterators instead of the container itself?

Passing vec.begin(), vec.end() instead of just vec means the SAME sort() function works identically on a vector, a portion of a vector (vec.begin(), vec.begin()+5), a deque, or even a raw array — one algorithm, any compatible container.

Section 2

std::sort — Ascending, Descending & Custom

By default, sort() arranges a range in ascending order using < comparisons.

sort_basics.cpp

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    sort(nums.begin(), nums.end()); // ascending by default
    for (int n : nums) cout << n << " ";
    cout << endl; // 1 2 3 5 8 9

    sort(nums.begin(), nums.end(), greater<int>()); // descending
    for (int n : nums) cout << n << " ";
    cout << endl; // 9 8 5 3 2 1

    return 0;
}

Passing greater<int>() as a third argument flips the comparison — the exact same trick you used to make a min-heap in Lesson 17. For anything more custom than "ascending" or "descending," pass a lambda instead.

sort_custom_lambda.cpp

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    // Sort by distance from 5, closest first
    sort(nums.begin(), nums.end(), [](int a, int b) {
        return abs(a - 5) < abs(b - 5);
    });

    for (int n : nums) cout << n << " ";
    cout << endl; // 5 3 2 8 1 9

    return 0;
}

✨

Reading a comparator lambda

The comparator answers one question: "should a come before b?" Return true if yes. sort() calls this repeatedly to figure out the final order — you never need to write the sorting logic yourself, just describe what "smaller" means for your data.

Section 3

std::find & std::binary_search

find() does a straightforward left-to-right scan (O(n)) and returns an iterator to the first match, or .end() if nothing matched. binary_search() is far faster — O(log n) — but it comes with one strict requirement.

find_and_binary_search.cpp

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {4, 8, 15, 16, 23, 42}; // already sorted!

    auto it = find(nums.begin(), nums.end(), 15);
    if (it != nums.end()) {
        cout << "Found 15 at index " << (it - nums.begin()) << endl;
    }

    // binary_search REQUIRES a sorted range to work correctly
    bool has23 = binary_search(nums.begin(), nums.end(), 23);
    cout << "Contains 23? " << (has23 ? "yes" : "no") << endl;

    return 0;
}

⚠️

Why binary_search NEEDS a sorted range

Binary search works by repeatedly checking the middle element and deciding "the target must be in the left half" or "the right half" — a decision that's only valid if the range is ordered. On unsorted data, that decision is meaningless and binary_search() can silently return the wrong answer. It won't warn you — sort first, always.

Section 4

max_element, min_element & reverse

A few more everyday tools: max_element() and min_element() return iterators to the largest and smallest values in a range (dereference with * to get the value). reverse() flips a range in place.

max_min_reverse.cpp

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    auto maxIt = max_element(nums.begin(), nums.end());
    auto minIt = min_element(nums.begin(), nums.end());

    cout << "Max: " << *maxIt << ", Min: " << *minIt << endl;

    reverse(nums.begin(), nums.end());

    for (int n : nums) cout << n << " ";
    cout << endl; // 3 9 1 8 2 5

    return 0;
}

🔀

sort()

Ascending by default. Pass greater<T>() or a lambda for any custom ordering.

🔎

find()

O(n) linear scan. Works on unsorted data. Returns .end() if not found.

⚡

binary_search()

O(log n). REQUIRES the range to already be sorted, or results are undefined.

↕️

max_element / min_element

Return iterators — dereference with * to get the actual value.

Section 5

Lesson Summary

✅Include <algorithm> for sort, find, binary_search, max/min_element, reverse and more.

✅sort() takes an optional comparator — greater<T>() for descending, or a lambda for anything custom.

✅find() works on any range, sorted or not, in O(n).

✅binary_search() is O(log n) but REQUIRES the range to already be sorted.

✅Algorithms operate on iterator ranges (.begin()/.end()), so the same function works across container types.

🧩 Knowledge Check — Lesson 18

Answer all 5 questions to test your understanding. Instant feedback on every answer.

1. Which header provides sort, find, binary_search, max_element and friends?

2. What must be true about a range BEFORE you call binary_search() on it?

3. How do you sort a vector<int> in DESCENDING order using the STL?

4. What does std::find() return if the element is NOT found in the range?

5. On a sorted vector, which is faster on average: std::find() or std::binary_search()?

💪

Coding Challenge — Lesson 18

Apply what you learned · Intermediate Level

Now it's your turn to write real code. Complete the challenge below in any C++ compiler.

Challenge: Sort Students by Score 🎓

Write a program that:

1. Defines a struct Student { string name; int score; };
2. Fills a vector<Student> with at least 4 students and different scores.
3. Uses std::sort with a lambda comparator to sort the vector by score, highest first.
4. Prints each student's name and score in the new sorted order.

Rules: Your comparator lambda must take two const Student& parameters and return a bool.

💡 Show hints if you're stuck

Comparator signature: [](const Student& a, const Student& b) { return a.score > b.score; } — returning > instead of < gives you descending order.
Call it like: sort(students.begin(), students.end(), yourComparator);
You can define the lambda inline as the third argument, or store it in a variable first — both work identically.

Finished this lesson?

Mark it complete to track your progress.

Module 18 of 26 Phase 4 — STL