SyntaxPilot
Courses/C++/Lesson 36
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ · Lesson 36 of 40

DSA 1: sorting and binary search with the STL

queued

These are the notes for C++ episode 36, the first DSA (data structures and algorithms) episode. A search that checks every item runs out of time, counting its steps explains why (time complexity and Big O), and the fix is binary search on sorted data: written by hand once (with its classic bug), then with the STL's sort, binary_search, lower_bound and upper_bound. Then sorting by your own rule with a lambda, and binary search on the answer. Every program was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the SyntaxPilot compiler's command) and run; outputs are copied from those runs. Times in milliseconds change from run to run and machine to machine; the ratios don't.

The problem: did anyone pay exactly this?

Ravi's ten stalls printed 200,000 bills this month. The tax auditor brings 200,000 amounts and asks, for each: did anyone pay exactly this? The obvious way checks every bill for every question:

#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main() {
    int n = 20000;                         // bills today
    vector<int> bills(n), asks(n);
    for (int i = 0; i < n; i++) {
        bills[i] = (i * 7919LL) % 1000000;   // bill amounts
        asks[i] = (i * 104729LL) % 2000000;  // amounts people ask about
    }
    auto start = steady_clock::now();
    int found = 0;
    for (int x : asks) {                   // every question...
        for (int b : bills) {              // ...checks every bill
            if (b == x) { found++; break; }
        }
    }
    auto ms = duration_cast<milliseconds>(steady_clock::now() - start).count();
    cout << "Found " << found << " of " << n << " in " << ms << " ms" << endl;
    return 0;
}
Found 203 of 20000 in 97 ms

With int n = 40000;:

Found 803 of 40000 in 391 ms

Twice the data, about four times the time. With int n = 200000; the SyntaxPilot compiler stops it: Time Limit Exceeded (8 seconds). On a laptop it needs about 10 seconds.

Time complexity and Big O

Count the steps. In the worst case each of the n questions checks all n bills: n × n steps.

n n × n steps
20,000 400,000,000
40,000 1,600,000,000 (4x)
200,000 40,000,000,000

A computer does very roughly 10⁸ to 10⁹ simple steps a second, so 4 × 10¹⁰ is far too slow.

Time complexity describes how the number of steps grows as the input size n grows. Big O notation keeps only the part that grows fastest and drops constants:

Big O Name n = 1,000,000 → about Example
O(1) constant 1 v[i]
O(log n) logarithmic 20 binary search
O(n) linear 1,000,000 checking every bill once
O(n log n) linearithmic 20,000,000 sort
O(n²) quadratic 1,000,000,000,000 a loop over all bills inside a loop over all questions

Double n: O(n) doubles, O(n²) quadruples, O(log n) adds one step.

Binary search: the idea

In a dictionary you don't start at page 1. Because words are in sorted order, you open the middle: "mango"; you want "pen", which comes later, so the whole left half is thrown away with one look. Repeat on what's left.

Every look halves the range. The number of times you can halve n until 1 is left is log₂ n:

Items Looks at most
10 4
1,000 10
1,000,000 20
1,000,000,000 30

So binary search is O(log n), and it only works on sorted data.

Binary search by hand

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

bool has(const vector<int>& a, int x) {
    int lo = 0, hi = a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // the middle page
        cout << "  look at a[" << mid << "] = " << a[mid] << endl;
        if (a[mid] == x) return true;
        if (a[mid] < x) lo = mid + 1;      // drop the left half
        else hi = mid - 1;                 // drop the right half
    }
    return false;
}

int main() {
    vector<int> bills = {20, 40, 60, 80, 120, 150, 200, 250, 300, 480};
    cout << "Find 250:" << endl;
    cout << (has(bills, 250) ? "yes" : "no") << endl;
    cout << "Find 90:" << endl;
    cout << (has(bills, 90) ? "yes" : "no") << endl;
    return 0;
}
Find 250:
  look at a[4] = 120
  look at a[7] = 250
yes
Find 90:
  look at a[4] = 120
  look at a[1] = 40
  look at a[2] = 60
  look at a[3] = 80
no
  • lo and hi mark the part that's still possible (both inclusive).
  • mid = lo + (hi - lo) / 2 is the same as (lo + hi) / 2, but can't overflow when lo + hi is bigger than the largest int.
  • Every step removes mid itself: lo = mid + 1 or hi = mid - 1.

The classic bug: forgetting + 1 / - 1

A safety counter stops it after 8 looks, so the output doesn't flood:

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

bool has(const vector<int>& a, int x) {
    int lo = 0, hi = a.size() - 1, looks = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        cout << "  look at a[" << mid << "] = " << a[mid] << endl;
        if (++looks == 8) { cout << "  ...still looking!" << endl; return false; }
        if (a[mid] == x) return true;
        if (a[mid] < x) lo = mid;          // forgot the + 1
        else hi = mid;                     // forgot the - 1
    }
    return false;
}

int main() {
    vector<int> bills = {20, 40, 60, 80, 120, 150, 200, 250, 300, 480};
    cout << "Find 90:" << endl;
    cout << (has(bills, 90) ? "yes" : "no") << endl;
    return 0;
}
Find 90:
  look at a[4] = 120
  look at a[2] = 60
  look at a[3] = 80
  look at a[3] = 80
  look at a[3] = 80
  look at a[3] = 80
  look at a[3] = 80
  look at a[3] = 80
  ...still looking!
no

With lo = 3, hi = 4, mid is 3; 80 < 90 so lo = mid = 3 again. The range never shrinks, so without the counter it loops forever.

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

int main() {
    int n = 200000;
    vector<int> bills(n), asks(n);
    for (int i = 0; i < n; i++) {
        bills[i] = (i * 7919LL) % 1000000;
        asks[i] = (i * 104729LL) % 2000000;
    }
    auto start = steady_clock::now();
    sort(bills.begin(), bills.end());      // sort once: n log n
    int found = 0;
    for (int x : asks) {
        if (binary_search(bills.begin(), bills.end(), x)) found++;
    }
    auto ms = duration_cast<milliseconds>(steady_clock::now() - start).count();
    cout << "Found " << found << " of " << n << " in " << ms << " ms" << endl;
    return 0;
}
Found 20009 of 200000 in 19 ms

The same job that ran out of time now takes milliseconds, sorting included. With int n = 2000000;:

Found 1000000 of 2000000 in 320 ms

Checking every bill, 2,000,000 questions would need about 4 × 10¹² steps: more than an hour. That is O(n²) against O(n log n) (sort once in n log n, then n searches of log n each).

Binary search on unsorted data: wrong, with no error

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

int main() {
    vector<int> bills = {150, 20, 480, 60, 300, 40};    // not sorted!
    cout << boolalpha;
    cout << "has 60?  " << binary_search(bills.begin(), bills.end(), 60) << endl;
    cout << "has 480? " << binary_search(bills.begin(), bills.end(), 480) << endl;
    return 0;
}
has 60?  false
has 480? false

Both are in the list. binary_search assumed the data was sorted and threw away the half that held them. Always sort first. (boolalpha prints true/false instead of 1/0.)

lower_bound and upper_bound

Think of students lined up by height:

  • lower_bound(b, e, x): an iterator to the first item ≥ x ("first student at least 150 cm").
  • upper_bound(b, e, x): an iterator to the first item > x ("first student taller than 150 cm").
  • Both return end() if there is no such item. Both are O(log n) and need sorted data.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> bills = {20, 40, 40, 60, 120, 150, 150, 150, 300, 480};

    auto first = lower_bound(bills.begin(), bills.end(), 150);  // first >= 150
    auto after = upper_bound(bills.begin(), bills.end(), 150);  // first >  150
    cout << "first 150 at index " << (first - bills.begin()) << endl;
    cout << "bills of exactly 150: " << (after - first) << endl;

    auto lo = lower_bound(bills.begin(), bills.end(), 50);
    auto hi = upper_bound(bills.begin(), bills.end(), 200);
    cout << "bills from 50 to 200: " << (hi - lo) << endl;

    auto big = lower_bound(bills.begin(), bills.end(), 1000);
    if (big == bills.end()) cout << "no bill of 1000 or more" << endl;
    return 0;
}
first 150 at index 5
bills of exactly 150: 3
bills from 50 to 200: 5
no bill of 1000 or more
  • it - v.begin() is the index.
  • upper_bound(x) - lower_bound(x) is how many items equal x.
  • upper_bound(hi) - lower_bound(lo) is how many items are in [lo, hi].
  • Always compare with end() before using *it.

Sorting by your own rule

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

struct Order {
    string name;
    int amount;
    int time;     // minute it arrived
};

int main() {
    vector<Order> orders = {{"Asha", 120, 5}, {"Ravi", 480, 9}, {"Neha", 120, 2},
                            {"Priya", 300, 7}, {"Kabir", 480, 1}};
    // biggest bill first; same bill: whoever came first
    sort(orders.begin(), orders.end(), [](const Order& a, const Order& b) {
        if (a.amount != b.amount) return a.amount > b.amount;
        return a.time < b.time;
    });
    for (const Order& o : orders)
        cout << o.name << " " << o.amount << " (minute " << o.time << ")" << endl;
    return 0;
}
Kabir 480 (minute 1)
Ravi 480 (minute 9)
Priya 300 (minute 7)
Neha 120 (minute 2)
Asha 120 (minute 5)

The third argument (a comparator) answers "should a come before b?". Without it, sorting a struct fails:

error: no match for 'operator<' (operand types are 'Order' and 'Order')

Comparator rules:

  • Return true only when a must come strictly before b. Never use >= or <= (that breaks sort, and can even crash it).
  • stable_sort keeps equal items in their original order; sort doesn't promise that.

Binary search on the answer

Ravi's tea factory has 2,000,000 office orders of 1 to 10,000 cups. Each order is brewed separately; an order bigger than the boiler takes several batches (rounded up: 5,000 cups in a 2,000-cup boiler = 3 batches). The factory can run 3,000,000 batches. What is the smallest boiler that's enough?

Trying every size from 1 upward:

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

// batches needed if the boiler holds k cups
long long batchesNeeded(const vector<int>& orders, long long k) {
    long long batches = 0;
    for (int cups : orders) batches += (cups + k - 1) / k;   // round up
    return batches;
}

int main() {
    int n = 2000000;                       // office orders this season
    vector<int> orders(n);
    for (int i = 0; i < n; i++) orders[i] = 1 + (i * 7919LL) % 10000;
    long long limit = 3000000;             // batches the factory can run
    for (long long k = 1; ; k++) {        // try every boiler size
        if (batchesNeeded(orders, k) <= limit) {
            cout << "Smallest boiler: " << k << " cups" << endl;
            break;
        }
    }
    return 0;
}

Result: Time Limit Exceeded. Each try walks 2,000,000 orders, and the answer is in the thousands.

The key observation: a bigger boiler never needs more batches. So the answers to "is size k enough?" go no, no, …, no, yes, yes, …, yes: they are sorted. Binary search for the first yes:

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

// batches needed if the boiler holds k cups
long long batchesNeeded(const vector<int>& orders, long long k) {
    long long batches = 0;
    for (int cups : orders) batches += (cups + k - 1) / k;   // round up
    return batches;
}

int main() {
    int n = 2000000;                       // office orders this season
    vector<int> orders(n);
    for (int i = 0; i < n; i++) orders[i] = 1 + (i * 7919LL) % 10000;
    long long limit = 3000000;             // batches the factory can run
    long long lo = 1, hi = 10000;         // the answer is in here
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (batchesNeeded(orders, mid) <= limit) hi = mid;  // fits
        else lo = mid + 1;                                  // too small
    }
    cout << "Smallest boiler: " << lo << " cups" << endl;
    return 0;
}
Smallest boiler: 5000 cups

About 14 tries (log₂ 10,000), each O(n): O(n log M) where M is the range of answers. Here the loop is while (lo < hi) and a "yes" keeps mid (hi = mid), because mid might be the answer; it still always shrinks since mid < hi.

Use this pattern when you're asked for the smallest (or largest) value that satisfies a condition, and the condition is monotonic (once true, always true).

Cheat sheet

Need Code Time
Sort ascending sort(v.begin(), v.end()); O(n log n)
Sort descending sort(v.begin(), v.end(), greater<int>()); O(n log n)
Sort by a rule sort(b, e, [](const T& a, const T& b){ return ...; }); O(n log n)
Keep ties in order stable_sort(b, e, cmp); O(n log n)
Is x there? binary_search(b, e, x) O(log n)
First ≥ x lower_bound(b, e, x) O(log n)
First > x upper_bound(b, e, x) O(log n)
How many equal x upper_bound(b, e, x) - lower_bound(b, e, x) O(log n)
Index of an iterator it - v.begin() O(1)
Safe middle lo + (hi - lo) / 2

Common mistakes

Mistake What you see Fix
binary_search on {150, 20, 480, 60, 300, 40} has 60? false sort first
lo = mid; / hi = mid; with while (lo <= hi) look at a[3] = 80 again and again, forever lo = mid + 1; / hi = mid - 1;
sort on a struct with no comparator error: no match for 'operator<' (operand types are 'Order' and 'Order') pass a lambda
A loop over all items inside a loop over all items, big n Time Limit Exceeded sort once, then binary search
Using *lower_bound(...) when x is bigger than everything reads past the end: undefined behaviour check it == v.end() first
(lo + hi) / 2 with huge ints overflow, a negative index lo + (hi - lo) / 2

Mini project: timing the four-times rule

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

int main() {
    for (int n = 10000; n <= 160000; n *= 2) {
        vector<int> bills(n), asks(n);
        for (int i = 0; i < n; i++) {
            bills[i] = (i * 7919LL) % 1000000;
            asks[i] = (i * 104729LL) % 2000000;
        }
        auto t0 = steady_clock::now();
        int slow = 0;
        for (int x : asks)
            for (int b : bills)
                if (b == x) { slow++; break; }
        auto t1 = steady_clock::now();
        sort(bills.begin(), bills.end());
        int fast = 0;
        for (int x : asks)
            if (binary_search(bills.begin(), bills.end(), x)) fast++;
        auto t2 = steady_clock::now();
        cout << n << ": slow " << duration_cast<milliseconds>(t1 - t0).count() << " ms, fast "
             << duration_cast<microseconds>(t2 - t1).count() << " us (" << slow << " = " << fast << ")" << endl;
    }
    return 0;
}

One run's output (a busy 2-core machine; your times will differ):

10000: slow 26 ms, fast 637 us (52 = 52)
20000: slow 147 ms, fast 1411 us (203 = 203)
40000: slow 522 ms, fast 3488 us (803 = 803)
80000: slow 2646 ms, fast 6602 us (3205 = 3205)
160000: slow 10859 ms, fast 13687 us (12800 = 12800)

Every doubling makes the slow search about 4 times slower (O(n²)), and the fast one only about 2 times slower (O(n log n)). Both find the same count. (us = microseconds, a thousandth of a millisecond.)

Practice

  1. Time both searches for n = 10,000 up to 160,000 and check the four-times rule (the mini project).
  2. Make 100,000 random marks from 0 to 100 and count the marks from 60 to 80 with lower_bound and upper_bound.
  3. Sort students by marks (highest first), then by name (A to Z).
  4. Ten books have 320, 150, 480, 210, 600, 90, 275, 410, 180 and 530 pages. You read one book at a time and never start a new book on the same day. What is the smallest number of pages a day that finishes all ten in 30 days?
Solutions

Exercise 2:

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

int main() {
    mt19937 gen(42);                            // fixed seed: same marks every run
    uniform_int_distribution<int> mark(0, 100);
    vector<int> marks(100000);
    for (int& m : marks) m = mark(gen);

    sort(marks.begin(), marks.end());
    auto lo = lower_bound(marks.begin(), marks.end(), 60);
    auto hi = upper_bound(marks.begin(), marks.end(), 80);
    cout << "Marks from 60 to 80: " << (hi - lo) << endl;
    return 0;
}
Marks from 60 to 80: 20795

(About 21 of the 101 possible marks fall in 60..80, so about 21% of 100,000.)

Exercise 3:

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

struct Student { string name; int marks; };

int main() {
    vector<Student> s = {{"Neha", 88}, {"Aarav", 92}, {"Kabir", 88}, {"Asha", 92}, {"Ravi", 75}};
    sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
        if (a.marks != b.marks) return a.marks > b.marks;   // higher marks first
        return a.name < b.name;                             // then A to Z
    });
    for (const Student& x : s) cout << x.name << " " << x.marks << endl;
    return 0;
}
Aarav 92
Asha 92
Kabir 88
Neha 88
Ravi 75

Exercise 4 (binary search on the answer):

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

long long daysNeeded(const vector<int>& books, long long perDay) {
    long long days = 0;
    for (int pages : books) days += (pages + perDay - 1) / perDay;  // one book at a time
    return days;
}

int main() {
    vector<int> books = {320, 150, 480, 210, 600, 90, 275, 410, 180, 530};
    long long lo = 1, hi = 600;                 // 600 pages a day finishes any book in a day
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (daysNeeded(books, mid) <= 30) hi = mid;
        else lo = mid + 1;
    }
    cout << "Read at least " << lo << " pages a day" << endl;
    cout << "Days needed: " << daysNeeded(books, lo) << endl;
    cout << "With " << lo - 1 << " pages a day: " << daysNeeded(books, lo - 1) << " days" << endl;
    return 0;
}
Read at least 133 pages a day
Days needed: 30
With 132 pages a day: 31 days

Quick quiz

vector<int> v = {10, 20, 20, 20, 30, 40};
auto a = lower_bound(v.begin(), v.end(), 20);
auto b = upper_bound(v.begin(), v.end(), 25);
cout << (a - v.begin()) << " " << (b - v.begin());

What does it print?

Answer

1 4. lower_bound(20) is the first item ≥ 20: index 1. upper_bound(25) is the first item > 25: the 30, at index 4. 25 doesn't have to be in the vector.

Interview questions

  1. Time complexity of binary search? O(log n), because every step halves the range.
  2. Why must the data be sorted? Throwing away half is only safe if everything on that side is too small (or too big); that is only true for sorted data.
  3. Linear vs binary search? Linear works on any data in O(n); binary needs sorted data and is O(log n). For one search on unsorted data, linear is better (sorting costs O(n log n)); for many searches, sort once and use binary search.
  4. lower_bound vs upper_bound? First element ≥ x vs first element > x.
  5. What algorithm does std::sort use? Introsort in libstdc++: quicksort that switches to heapsort when it recurses too deep and to insertion sort for small parts; O(n log n) guaranteed, not stable.
  6. Stable sort? Equal elements keep their original order; std::stable_sort (a merge sort).
  7. What is binary search on the answer? Searching the range of possible answers for the first one that satisfies a monotonic yes/no check.
  8. How do you avoid overflow in mid? lo + (hi - lo) / 2.

Glossary

Term Meaning, with an example
DSA Data structures and algorithms: ways to store data and to work with it fast.
algorithm A step-by-step method, like binary search.
linear search Checking items one by one. O(n).
time complexity How the number of steps grows with the input size n.
Big O notation Writing that growth with constants dropped: O(n), O(n²), O(log n).
O(n²) Quadratic: double n, 4x the time. A loop inside a loop.
logarithm (log₂ n) How many times you can halve n until 1 is left: log₂ 1,000,000 ≈ 20.
O(log n) Logarithmic: binary search.
O(n log n) The time of a good sort.
sorted In order, smallest to largest (or by a rule).
binary search Look at the middle, throw away the half that can't hold the answer, repeat.
lo, hi, mid The ends of the range still possible, and its middle.
off-by-one error A bug from being one position off, like lo = mid instead of mid + 1.
integer overflow A result too big for its type; lo + hi can overflow an int.
std::sort Sorts a range in O(n log n) (<algorithm>).
std::binary_search True/false: is x in the sorted range?
lower_bound Iterator to the first item ≥ x.
upper_bound Iterator to the first item > x.
iterator A position in a container; it - v.begin() gives its index.
comparator A function or lambda telling sort whether a goes before b.
stable_sort A sort that keeps equal items in their original order.
Time Limit Exceeded (TLE) The judge stopped a program that ran too long.
monotonic Only goes one way: once yes, always yes.
binary search on the answer Binary search over possible answers, using a monotonic yes/no check.
boolalpha Makes cout print true/false.
steady_clock A clock for measuring durations (<chrono>).

Summary

  • Count the steps: a loop over n inside a loop over n is O(n²): double n, 4x the time.
  • Binary search halves the range every look: O(log n), about 20 looks for a million, only on sorted data.
  • Write it with lo + (hi - lo) / 2, and always move past mid.
  • STL: sort once (O(n log n)), then binary_search, lower_bound (first ≥ x) and upper_bound (first > x).
  • Sort by any rule with a lambda comparator; stable_sort keeps ties in order.
  • Binary search on the answer when the yes/no answers are sorted: no…no, yes…yes.

Next episode: Raju the delivery boy needs the shortest route through the lanes. DSA 2: graphs.