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
loandhimark the part that's still possible (both inclusive).mid = lo + (hi - lo) / 2is the same as(lo + hi) / 2, but can't overflow whenlo + hiis bigger than the largestint.- Every step removes
miditself:lo = mid + 1orhi = 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.
The STL: sort + binary_search
#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
trueonly when a must come strictly before b. Never use>=or<=(that breakssort, and can even crash it). stable_sortkeeps equal items in their original order;sortdoesn'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
- Time both searches for n = 10,000 up to 160,000 and check the four-times rule (the mini project).
- Make 100,000 random marks from 0 to 100 and count the marks from 60 to 80 with
lower_boundandupper_bound. - Sort students by marks (highest first), then by name (A to Z).
- 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
- Time complexity of binary search? O(log n), because every step halves the range.
- 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.
- 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.
lower_boundvsupper_bound? First element ≥ x vs first element > x.- What algorithm does
std::sortuse? 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. - Stable sort? Equal elements keep their original order;
std::stable_sort(a merge sort). - What is binary search on the answer? Searching the range of possible answers for the first one that satisfies a monotonic yes/no check.
- 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 pastmid. - STL:
sortonce (O(n log n)), thenbinary_search,lower_bound(first ≥ x) andupper_bound(first > x). - Sort by any rule with a lambda comparator;
stable_sortkeeps 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.