These are the notes for C++ Coding Questions, episode 12, placement practice for people who finished the SyntaxPilot C++ course. Binary search: the idea fits in one sentence ("look at the middle, throw away half"), but the details trip up almost everyone. Today: the search insert position (and an off-by-one that loses the answer n), the first and last occurrence of a number and its count with lower_bound and upper_bound, and the integer square root of numbers up to 10¹⁸ with binary search on the answer (where sqrt and mid * mid both give wrong results).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.
Real-life pictures
| In real life | In C++ |
|---|---|
| A library shelf sorted by book number: where does book 640 go? | search insert position: the first index with v[i] >= x |
| Walking the shelf book by book | a linear scan, O(n) |
| Looking at the middle book and throwing away half the shelf | binary search, O(log n): 1,000 books → about 10 looks |
| The first page of the "m" words in a dictionary | lower_bound(x): the first element >= x |
| The first page after the "m" words | upper_bound(x): the first element > x |
| How many "m" pages: end page − start page | count = upper - lower (0 means x isn't there) |
| The "I'm thinking of a number" game: you may only ask "is r × r too big?" | binary search on the answer |
The one requirement
Binary search needs a yes/no question that flips exactly once along the range: no, no, no, ..., yes, yes, yes. Binary search finds where it flips.
- "Is
v[i] >= x?" on a sorted vector (Q1, Q2). - "Is
r * r > n?" for r = 1, 2, 3, ... (Q3). - "Can a truck of capacity c ship everything in 3 trips?" (your turn).
Q1: Search insert position
Problem. Given a sorted vector and queries x, print for each x the first index i with v[i] >= x (where x would be inserted to keep the vector sorted).
| v = 1 3 5 7 9 | x = 5 | 4 | 0 | 10 | 9 |
|---|---|---|---|---|---|
| answer | 2 | 2 | 0 | 5 | 4 |
Think out loud. x smaller than everything → 0. x bigger than everything → n (5 here), which is not a valid index. Big test: 300,000 numbers and 300,000 queries (the test block, when n is 0, builds them; every query is past the end, and it prints only the last answer).
The obvious attempt: walk the shelf
#include <iostream>
#include <vector>
using namespace std;
int firstAtLeast(const vector<int>& v, int x) {
int i = 0;
while (i < (int)v.size() && v[i] < x) i++;
return i;
}
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { // test: 300,000 numbers and queries
n = q = 300000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
}
for (int k = 0; k < q; k++) {
int x = 1000000;
if (!big) cin >> x;
int p = firstAtLeast(v, x);
if (!big || k == q - 1) cout << p << " ";
}
cout << "\n";
return 0;
}
Input 5 5 / 1 3 5 7 9 / 5 4 0 10 9:
2 2 0 5 4
Now 0 0 (the big test):
Time Limit Exceeded (no output: the program was stopped)
Why. Every query walks up to n numbers: 300,000 × 300,000 = 90 billion steps.
Attempt: binary search with hi = n - 1
#include <iostream>
#include <vector>
using namespace std;
int firstAtLeast(const vector<int>& v, int x) {
int lo = 0, hi = v.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { // test: 300,000 numbers and queries
n = q = 300000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
}
for (int k = 0; k < q; k++) {
int x = 1000000;
if (!big) cin >> x;
int p = firstAtLeast(v, x);
if (!big || k == q - 1) cout << p << " ";
}
cout << "\n";
return 0;
}
2 2 0 4 4
The fourth answer is 4, but 10 goes after 9, at index 5.
Why. hi = n - 1 says "the answer is one of the indexes 0 to n − 1". But the answer can be n itself (after everything), so it was never in the range: lo can never reach 5.
Fix: the answer is in [lo, hi] with hi = n
the answer is somewhere in lo..hi, with hi = n; loop while lo < hi
v[mid] < x → lo = mid + 1 (mid is too small, and so is everything left of it)
otherwise → hi = mid (mid might be the answer: keep it)
mid = lo + (hi - lo) / 2 is always < hi <= n, so v[mid] is always a valid index
#include <iostream>
#include <vector>
using namespace std;
int firstAtLeast(const vector<int>& v, int x) {
int lo = 0, hi = v.size(); // answer is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] < x) lo = mid + 1;
else hi = mid;
}
return lo;
}
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { // test: 300,000 numbers and queries
n = q = 300000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
}
for (int k = 0; k < q; k++) {
int x = 1000000;
if (!big) cin >> x;
int p = firstAtLeast(v, x);
if (!big || k == q - 1) cout << p << " ";
}
cout << "\n";
return 0;
}
2 2 0 5 4
300000
300,000 (= n, past the end), instantly: about 19 looks per query instead of up to 300,000.
The same thing in the STL: std::lower_bound
lower_bound(first, last, x) returns an iterator to the first element not less than x (>= x), or last if there is none. Subtract v.begin() to get the index.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int firstAtLeast(const vector<int>& v, int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int& x : v) cin >> x;
bool big = (n == 0);
if (big) { // test: 300,000 numbers and queries
n = q = 300000;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = 2 * i;
}
for (int k = 0; k < q; k++) {
int x = 1000000;
if (!big) cin >> x;
int p = firstAtLeast(v, x);
if (!big || k == q - 1) cout << p << " ";
}
cout << "\n";
return 0;
}
2 2 0 5 4
Complexity. O(log n) per query, O(1) extra space. The vector must be sorted (by the same order you search with); on unsorted data the answers are meaningless.
Q2: First and last occurrence, and the count
Problem. In a sorted vector, print the first index of x, the last index of x and how many times x appears, each in O(log n). If x is missing: -1 -1, count 0.
| v = 1 2 2 2 2 3 5 | x = 2 | 5 | 4 | 1 | 6 |
|---|---|---|---|---|---|
| first last, count | 1 4, 4 | 6 6, 1 | -1 -1, 0 | 0 0, 1 | -1 -1, 0 |
The obvious attempt: the textbook binary search
#include <iostream>
#include <vector>
using namespace std;
int find(const vector<int>& v, int x) {
int lo = 0, hi = (int)v.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] == x) return mid;
if (v[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
int main() {
vector<int> v = {1, 2, 2, 2, 2, 3, 5};
int x;
while (cin >> x) cout << x << ": first at " << find(v, x) << "\n";
return 0;
}
Input 2 5 4 1 6:
2: first at 3
5: first at 6
4: first at -1
1: first at 0
6: first at -1
2: first at 3, but 2 first appears at index 1.
Why. The first mid is index 3, which holds a 2, so the search stops. "Equal" doesn't mean "first": there may be more copies to the left (and to the right). This search finds any copy.
Fix: lower_bound and upper_bound
- first =
lower_bound(x)(first>= x) - last =
upper_bound(x) - 1(upper_bound(x)is the first> x) - count =
upper_bound(x) - lower_bound(x); if they are equal, x is missing.
Never read *lower_bound(...) without checking: for x bigger than everything it is v.end(), and reading it is undefined behaviour.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 2, 2, 2, 2, 3, 5};
int x;
while (cin >> x) {
int lo = lower_bound(v.begin(), v.end(), x) - v.begin();
int up = upper_bound(v.begin(), v.end(), x) - v.begin();
if (lo == up) cout << x << ": -1 -1, count 0\n";
else cout << x << ": " << lo << " " << up - 1 << ", count " << up - lo << "\n";
}
return 0;
}
2: 1 4, count 4
5: 6 6, count 1
4: -1 -1, count 0
1: 0 0, count 1
6: -1 -1, count 0
Complexity. Two binary searches: O(log n) time, O(1) extra space. (std::equal_range(v.begin(), v.end(), x) returns both iterators at once.)
Hand-written version of upper_bound: exactly Q1's loop with v[mid] <= x instead of v[mid] < x.
Q3: Integer square root
Problem. For n from 0 to 10¹⁸, print the largest whole number r with r × r ≤ n.
| n | 16 | 15 | 0 | 1 | 999999999999999999 |
|---|---|---|---|---|---|
| answer | 4 | 3 | 0 | 1 | 999999999 |
The obvious attempt: sqrt from <cmath>
#include <iostream>
#include <cmath>
using namespace std;
long long isqrt(long long n) {
return (long long)sqrt(n);
}
int main() {
long long n;
while (cin >> n) cout << n << " -> " << isqrt(n) << "\n";
return 0;
}
Input 16 15 0 1 999999999999999999:
16 -> 4
15 -> 3
0 -> 0
1 -> 1
999999999999999999 -> 1000000000
For eighteen nines it prints 1000000000, but 1,000,000,000² = 10¹⁸ > n: one too big.
Why. sqrt works on a double, which has a 53-bit mantissa: about 15 to 16 exact decimal digits. 999,999,999,999,999,999 doesn't fit, so converting it to a double rounds it up to exactly 10¹⁸, whose square root is exactly 10⁹.
Attempt: binary search on the answer, with mid * mid
Search r in [0, n]: if mid * mid <= n, mid might be the answer, remember it and go higher; otherwise go lower.
#include <iostream>
using namespace std;
long long isqrt(long long n) {
long long lo = 0, hi = n, ans = 0;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
if (mid * mid <= n) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}
int main() {
long long n;
while (cin >> n) cout << n << " -> " << isqrt(n) << "\n";
return 0;
}
16 -> 4
15 -> 3
0 -> 0
1 -> 1
999999999999999999 -> 52636257926394405
The small numbers are right; for eighteen nines the root is completely wrong.
Why. The first mid is about 5 × 10¹⁷ and mid * mid is about 2.5 × 10³⁵, far beyond the long long maximum (about 9.2 × 10¹⁸). Signed overflow is undefined behaviour: the comparison means nothing, and the search goes the wrong way.
Fix: divide instead of multiplying
mid <= n / midasks the same question asmid * mid <= n(for whole numbers and mid ≥ 1), with no overflow. Solostarts at 1 (no division by zero); for n = 0 the loop doesn't run and the answer stays 0.mid = lo + (hi - lo) / 2instead of(lo + hi) / 2:lo + hican overflow too when both are near the maximum.
#include <iostream>
using namespace std;
long long isqrt(long long n) {
long long lo = 1, hi = n, ans = 0;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
if (mid <= n / mid) { ans = mid; lo = mid + 1; } // mid * mid <= n
else hi = mid - 1;
}
return ans;
}
int main() {
long long n;
while (cin >> n) cout << n << " -> " << isqrt(n) << "\n";
return 0;
}
16 -> 4
15 -> 3
0 -> 0
1 -> 1
999999999999999999 -> 999999999
Complexity. O(log n): about 60 guesses for n = 10¹⁸. O(1) extra space.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| insert position, walk the shelf | O(n) per query | O(1) |
insert position, binary search / lower_bound |
O(log n) per query | O(1) |
first, last, count (lower_bound, upper_bound) |
O(log n) | O(1) |
| first, last, count by scanning | O(n) | O(1) |
square root, (long long)sqrt(n) |
O(1) but wrong near 10¹⁸ | O(1) |
| square root, binary search on the answer | O(log n) ≈ 60 steps | O(1) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| a linear scan per query on big inputs | Time Limit Exceeded | q × n steps | binary search, O(log n) |
hi = n - 1 for an insert position |
10 → 4 (should be 5) |
n was left out of the range | hi = n, while (lo < hi) |
if (v[mid] == x) return mid; for "first" |
2: first at 3 |
stops at any copy | lower_bound; last = upper_bound - 1 |
*lower_bound(...) without a check |
garbage or a crash | it can be v.end() |
compare with v.end() / lower == upper |
(long long)sqrt(n) for n near 10¹⁸ |
1000000000 (one too big) |
a double has 53 bits |
integer binary search |
mid * mid <= n |
a completely wrong root | signed overflow (UB) | mid <= n / mid |
mid = (lo + hi) / 2 near the maximum |
overflow (UB) | lo + hi too big |
lo + (hi - lo) / 2 |
| binary search on unsorted data | wrong answers, no error | the yes/no doesn't flip once | sort first |
Your turn: the smallest truck (solution)
Problem. Parcels must be shipped in order in at most trips trips; each trip carries parcels whose total weight is at most the truck capacity c. What is the smallest c that works? 3 2 2 4 1 4 with 3 trips → 6 (3 2 | 2 4 | 1 4; with 5 you need 4 trips: 3 2 | 2 | 4 1 | 4).
Idea. "Can capacity c do it in 3 trips?" is no, no, no, then yes, yes, yes as c grows: binary search on c. Checking one c is a greedy walk (fill the truck until the next parcel doesn't fit). The answer is between the heaviest parcel (anything smaller can't carry it) and the total weight (one trip).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// can a truck of capacity c ship every parcel, in order, in at most `trips` trips?
bool canShip(const vector<int>& w, long long c, int trips) {
int used = 1;
long long load = 0;
for (int x : w) {
if (load + x > c) { used++; load = 0; } // start a new trip
load += x;
}
return used <= trips;
}
int main() {
int n, trips;
while (cin >> n >> trips) {
vector<int> w(n);
for (int& x : w) cin >> x;
long long lo = *max_element(w.begin(), w.end()); // must carry the heaviest parcel
long long hi = 0;
for (int x : w) hi += x; // one trip carries everything
while (lo < hi) { // answer is in [lo, hi]
long long mid = lo + (hi - lo) / 2;
if (canShip(w, mid, trips)) hi = mid; // works: maybe smaller works too
else lo = mid + 1; // too small
}
cout << lo << "\n";
}
return 0;
}
Input 6 3 / 3 2 2 4 1 4 and 10 5 / 1 2 3 4 5 6 7 8 9 10:
6
15
O(n log S) time, where S is the total weight. O(1) extra space.
Practice questions (with solutions)
1. The peak of a mountain array (numbers go strictly up, then strictly down). "Is v[mid] < v[mid + 1]?" (still climbing) flips once.
Solution
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> v(n);
for (int& x : v) cin >> x;
int lo = 0, hi = n - 1; // the peak is in [lo, hi]
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] < v[mid + 1]) lo = mid + 1; // still climbing: the peak is to the right
else hi = mid; // going down (or at the top): mid might be it
}
cout << "peak at index " << lo << ": " << v[lo] << "\n";
}
return 0;
}
peak at index 3: 9
peak at index 3: 4
2. Search in a rotated sorted vector (distinct numbers, sorted and then rotated, like 15 18 22 3 5 8 11). One half around mid is always sorted: check whether x lies inside it.
Solution
#include <iostream>
#include <vector>
using namespace std;
int search(const vector<int>& v, int x) {
int lo = 0, hi = (int)v.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] == x) return mid;
if (v[lo] <= v[mid]) { // the left half lo..mid is sorted
if (v[lo] <= x && x < v[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // the right half mid..hi is sorted
if (v[mid] < x && x <= v[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
int main() {
vector<int> v = {15, 18, 22, 3, 5, 8, 11}; // distinct numbers, sorted then rotated
int x;
while (cin >> x) cout << x << " -> " << search(v, x) << "\n";
return 0;
}
5 -> 4
15 -> 0
11 -> 6
4 -> -1
O(log n).
3. Koko eating bananas: the smallest eating speed k (bananas per hour, one pile at a time) to finish all piles in h hours. Binary search on k; hours for a pile = ⌈p / k⌉ = (p + k - 1) / k.
Solution
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long hoursNeeded(const vector<int>& piles, long long k) {
long long h = 0;
for (int p : piles) h += (p + k - 1) / k; // ceil(p / k) without doubles
return h;
}
int main() {
int n; long long h;
while (cin >> n >> h) {
vector<int> piles(n);
for (int& p : piles) cin >> p;
long long lo = 1, hi = *max_element(piles.begin(), piles.end());
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (hoursNeeded(piles, mid) <= h) hi = mid; // fast enough: try slower
else lo = mid + 1;
}
cout << lo << "\n";
}
return 0;
}
Input 4 8 / 3 6 7 11 and 5 5 / 30 11 23 4 20:
4
30
Mini project: how many students scored from a to b?
Sort the marks once, then every question is two binary searches: upper_bound(b) - lower_bound(a).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> marks(n);
for (int& m : marks) cin >> m;
sort(marks.begin(), marks.end()); // binary search needs sorted data
int a, b;
while (cin >> a >> b) { // how many scored from a to b?
auto from = lower_bound(marks.begin(), marks.end(), a); // first >= a
auto to = upper_bound(marks.begin(), marks.end(), b); // first > b
long long k = to - from;
cout << a << "-" << b << ": " << k << (k == 1 ? " student\n" : " students\n");
}
return 0;
}
Input: 8 marks 45 90 72 66 90 38 81 72, then 70 90, 0 39, 91 100:
70-90: 5 students
0-39: 1 student
91-100: 0 students
Quick quiz
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {1, 3, 3, 3, 8};
cout << lower_bound(v.begin(), v.end(), 3) - v.begin()
<< upper_bound(v.begin(), v.end(), 3) - v.begin()
<< lower_bound(v.begin(), v.end(), 9) - v.begin();
cout << "\n";
return 0;
}
(A) 135 (B) 143 (C) 145 (D) 034
Answer
(C) 145. lower_bound(3) = 1 (the first element >= 3), upper_bound(3) = 4 (the first > 3, the 8), and lower_bound(9) = 5 = v.size(), past the end, because 9 is bigger than everything.
145
Interview questions
- What does binary search need? Sorted data, or more generally a yes/no condition that flips exactly once over the range.
lower_boundvsupper_bound? The first element>= xvs the first element> x. Both returnend()if there is none.- Count the occurrences of x in a sorted vector in O(log n).
upper_bound(x) - lower_bound(x)(orequal_range). - Why
mid = lo + (hi - lo) / 2?lo + hican overflow when both are large; this form can't. - What is binary search on the answer? Searching over the possible answers instead of an array, using a check "is c good enough?" that flips once (square root, minimum capacity, minimum speed).
- Why is
(long long)sqrt(n)unsafe for big n? Adoublekeeps only 53 bits (about 15-16 digits); big integers get rounded beforesqrteven runs. - How many steps does binary search take on 10⁶ elements? On 10¹⁸ possible answers? About 20; about 60.
std::binary_searchreturns only abool. How do you get the index?lower_bound, then check that it isn'tend()and that*it == x.- Does
std::set/std::maphave its ownlower_bound? Yes,s.lower_bound(x): O(log n). Callingstd::lower_bound(s.begin(), s.end(), x)on a set is O(n), because its iterators can't jump.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Binary search | Look at the middle, throw away the half that can't hold the answer | 1,000 books → about 10 looks |
| Search insert position | The first index with v[i] >= x |
10 in 1 3 5 7 9 → 5 |
std::lower_bound |
Iterator to the first element >= x (or end()) |
lower_bound(v.begin(), v.end(), x) |
std::upper_bound |
Iterator to the first element > x (or end()) |
upper_bound(v.begin(), v.end(), x) |
std::equal_range |
Both bounds at once, as a pair | auto [a, b] = equal_range(...) |
| Iterator | A position in a container, like a pointer | v.begin(), v.end() |
it - v.begin() |
Turns a vector iterator into an index | lower_bound(...) - v.begin() |
v.end() |
The position just past the last element; never read it | *v.end() is UB |
| First / last occurrence | The smallest / largest index holding x | 2 in 1 2 2 2 2 3 5 → 1 and 4 |
| Off-by-one error | An answer wrong by exactly one | 10 → 4 instead of 5 |
| Binary search on the answer | Binary search over possible answers with a yes/no check | integer square root |
| Integer square root | The largest r with r × r ≤ n | 15 → 3 |
double |
A 64-bit floating-point number with a 53-bit mantissa | about 15-16 exact digits |
long long |
A 64-bit integer, up to about 9.2 × 10¹⁸ | long long n |
| Signed overflow | A signed result too big for its type: undefined behaviour | mid * mid for mid ≈ 5 × 10¹⁷ |
| Undefined behaviour (UB) | Code the C++ standard gives no meaning to | overflow, reading *v.end() |
| O(log n) | Work grows by one step each time n doubles | 300,000 → 19 steps |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | a linear scan per query |
Summary
- Insert position: the answer can be n, so search with
hi = nandwhile (lo < hi);std::lower_bounddoes exactly this. - First / last / count:
lower_bound(x),upper_bound(x) - 1,upper - lower; equal bounds mean x is missing. The textbook "return mid" search finds any copy. - Binary search on the answer: a yes/no question that flips once. For the square root use integers,
mid <= n / midandlo + (hi - lo) / 2;sqrtandmid * midare wrong near 10¹⁸. - Test the edges: before everything, after everything, missing values, the biggest inputs.
Next episode: Map and set questions: word frequency (map vs unordered_map order), the first repeating element with a set, and grouping anagrams with a map of sorted keys.