SyntaxPilot
Courses/C++ Coding Questions/Lesson 12
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++ Coding Questions · Lesson 12 of 30

Binary search questions

lower_bound and upper_boundfirst/last occurrence and countbinary search on the answer (integer square root, mid overflow)

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
#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 / mid asks the same question as mid * mid <= n (for whole numbers and mid ≥ 1), with no overflow. So lo starts at 1 (no division by zero); for n = 0 the loop doesn't run and the answer stays 0.
  • mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2: lo + hi can 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

  1. What does binary search need? Sorted data, or more generally a yes/no condition that flips exactly once over the range.
  2. lower_bound vs upper_bound? The first element >= x vs the first element > x. Both return end() if there is none.
  3. Count the occurrences of x in a sorted vector in O(log n). upper_bound(x) - lower_bound(x) (or equal_range).
  4. Why mid = lo + (hi - lo) / 2? lo + hi can overflow when both are large; this form can't.
  5. 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).
  6. Why is (long long)sqrt(n) unsafe for big n? A double keeps only 53 bits (about 15-16 digits); big integers get rounded before sqrt even runs.
  7. How many steps does binary search take on 10⁶ elements? On 10¹⁸ possible answers? About 20; about 60.
  8. std::binary_search returns only a bool. How do you get the index? lower_bound, then check that it isn't end() and that *it == x.
  9. Does std::set / std::map have its own lower_bound? Yes, s.lower_bound(x): O(log n). Calling std::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 = n and while (lo < hi); std::lower_bound does 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 / mid and lo + (hi - lo) / 2; sqrt and mid * mid are 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.