C++ Module 19 – C++ for DSA and competitive programming

C++ binary search: lower_bound and partition_point

Use lower_bound, upper_bound, equal_range and partition_point on sorted data, binary-search on the answer over iota, and avoid off-by-one and overflow bugs.

Intermediate
20 minutes
Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
By MySmartCoPilot

Free: The four searches land where a value is, or would go · Search the answers instead of the data · Five search mistakes that report no error · Practise. With a pass: 2 in-depth parts and 3 interview answers, about 13 minutes.

What you will learn

Use lower_bound, upper_bound, equal_range and binary_search correctly on sorted data
Search for the answer to a problem with partition_point over views::iota
Avoid off-by-one, comparator and overflow mistakes in binary searches

Before you start

What you’ll learn · Before you start

What you will learn

Use lower_bound, upper_bound, equal_range and binary_search correctly on sorted data
Search for the answer to a problem with partition_point over views::iota
Avoid off-by-one, comparator and overflow mistakes in binary searches

Before you start

On this page

The standard library binary-searches a sorted range for you, in about log₂ n comparisons: about 20 for a million elements. std::lower_bound returns the first element that is not less than the value you ask for, std::upper_bound returns the first element that is greater, std::equal_range returns both at once, and std::binary_search only says whether the value is there. The first element of a partitioned range for which a test is false, where the run of elements that pass the test ends. std::partition_point finds it by halving the range. is the general form behind all four: on a range where a test holds for a run of elements at the front and fails for the rest, it returns the first element for which the test fails. Run it over view: A range that does not own its elements: it refers to elements stored elsewhere or computes them, is cheap to copy, and does its work only while it is iterated, as std::views::filter and std::views::iota do. More in “C++ views and pipelines: filter, transform, iota”, which produces the numbers from lo up to, but not including, hi, and it searches numbers instead of an array. That is Finding the smallest value that works, such as a time, a capacity or a daily limit, by halving a range of candidates with a yes-or-no test instead of searching stored data., the usual way to find the smallest value that works in a contest or an interview problem. Each function also has a std::ranges form that takes a whole range. Prefer them to a loop written by hand, because hand-written loops are where off-by-one errors, endless loops and overflowing middles come from.

The four searches land where a value is, or would go

Where each search lands in the sorted marks of bounds.cpp

Text description of the diagram

A table with one row per position of the sorted vector of marks 35, 42, 42, 42, 58, 63, 63, 71, 88 and 95, and a last row for position 10, just past the end.

Position 0 holds 35. lower_bound(30) returns it, because 35 is the first mark not less than 30.
Position 1 holds the first 42. lower_bound(42) returns it, and equal_range(42) starts here.
Positions 2 and 3 hold the other two 42s, inside equal_range(42).
Position 4 holds 58. upper_bound(42) returns it, the first mark greater than 42, and equal_range(42) ends here, so 42 appears 4 − 1 = 3 times.
Position 5 holds the first 63. Both lower_bound(60) and upper_bound(60) return it: 60 is not in the vector, so both bounds point to where it would be inserted.
Position 7 holds 71, which upper_bound(63) returns.
Positions 6, 8 and 9 (63, 88 and 95) are not returned by any of these searches.
Position 10 is past the end, the value of marks.size(). lower_bound(99) returns it, because no mark is 99 or more.

bounds.cpp C++ · bounds.cpp

// The four binary-search functions on one sorted vector of exam marks.
#include <algorithm>
#include <print>
#include <vector>

int main() {
  const std::vector<int> marks{35, 42, 42, 42, 58, 63, 63, 71, 88, 95};

  // Positions are offsets from begin(); marks.size() means "past the end".
  auto pos = [&](auto it) { return it - marks.begin(); };

  std::println("lower_bound(42) = {}", pos(std::lower_bound(marks.begin(), marks.end(), 42)));
  std::println("upper_bound(42) = {}", pos(std::upper_bound(marks.begin(), marks.end(), 42)));
  auto [first, last] = std::equal_range(marks.begin(), marks.end(), 42);
  std::println("equal_range(42) = [{}, {}), so 42 appears {} times", pos(first), pos(last), last - first);

  // A value that is not there: both bounds point to where it would go.
  std::println("lower_bound(60) = {}, upper_bound(60) = {}",
               pos(std::ranges::lower_bound(marks, 60)), pos(std::ranges::upper_bound(marks, 60)));
  std::println("binary_search(60) = {}, binary_search(63) = {}",
               std::ranges::binary_search(marks, 60), std::ranges::binary_search(marks, 63));

  // Past every element: the "position" is marks.size().
  std::println("lower_bound(99) = {} (the size is {})", pos(std::ranges::lower_bound(marks, 99)), marks.size());

  // How many marks lie in [40, 65]? Two searches and one subtraction.
  auto from = std::ranges::lower_bound(marks, 40);
  auto to = std::ranges::upper_bound(marks, 65);
  std::println("marks from 40 to 65: {}", to - from);
}

The four searches, with both compilers Python · bounds_session.py

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra bounds.cpp -o bounds && ./bounds
g++-16 -std=c++23 -Wall -Wextra bounds.cpp -o bounds-gcc && ./bounds-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra bounds.cpp -o bounds && ./bounds
lower_bound(42) = 1
upper_bound(42) = 4
equal_range(42) = [1, 4), so 42 appears 3 times
lower_bound(60) = 5, upper_bound(60) = 5
binary_search(60) = false, binary_search(63) = true
lower_bound(99) = 10 (the size is 10)
marks from 40 to 65: 6
$ g++-16 -std=c++23 -Wall -Wextra bounds.cpp -o bounds-gcc && ./bounds-gcc
lower_bound(42) = 1
upper_bound(42) = 4
equal_range(42) = [1, 4), so 42 appears 3 times
lower_bound(60) = 5, upper_bound(60) = 5
binary_search(60) = false, binary_search(63) = true
lower_bound(99) = 10 (the size is 10)
marks from 40 to 65: 6

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 bounds_session.py

The first 42 sits at position 1, which is what lower_bound returned, and upper_bound returned position 4, the first mark after the run of 42s. So equal_range gives the half-open range: A range written [first, last) that includes its first position and stops before its last, like a loop from marks to marks + 5. It holds last - first elements, and it is empty when first == last. More in “Pointer arithmetic, arrays and std::span” [1, 4), and its length, 3, is the number of 42s. An absent value has no element to point at: both bounds of 60 are position 5, where 60 would have to go to keep the vector sorted, and binary_search says false. When every element is smaller than the value, the bounds return the end, position 10 here, so check for the end before you read the element. Two searches also count a range of values: the marks from 40 to 65 are the ones from lower_bound(40) up to, but not including, upper_bound(65), six of them, found with about 2 log₂ n comparisons however many marks there are.

The figure runs the classic search on the same marks; it stops at the first equal mark it probes. For 60 it ends with hi = 4 just left of lo = 5, where both bounds of 60 pointed. Type 42, or your own marks:

Interactive · step through it The classic search for 60 in the ten sorted marks Each probe halves the range where the target can still be; the dimmed values are ruled out.

being compared or looked at
visited or ruled out

Pseudo-code

lo ← 0; hi ← n − 1
while lo ≤ hi:
mid ← lo + ⌊(hi − lo) / 2⌋
if a[mid] = target: return mid
if a[mid] < target: lo ← mid + 1
else: hi ← mid − 1
return "not found"

Look for 60. The invariant: if 60 is in the array, it is somewhere in a[lo..hi]. At the start that range is the whole array, positions 0 to 9.

When it finishes: 60 not found.

Probes 0

Positions left 10

The four searches of a sorted range
Criterion	lower_bound(x)	upper_bound(x)	equal_range(x)	binary_search(x)
Returns	The first element not less than x	The first element greater than x	Both, as a pair	true or false
When x is absent	Where x would be inserted	The same position	An empty range at that position	false
Comparisons at most	log₂ n + O(1)	log₂ n + O(1)	2 log₂ n + O(1)	log₂ n + O(1)
When to choose	Find x, or the next value after it	The end of a run of equal values	Count or visit every copy of x	A yes-or-no membership test

All four need the range to be sorted by the same order they compare with, which is < unless you pass a comparator: A function that takes two elements and returns true when the first must come before the second, such as [](int a, int b) { return a > b; } for the highest first. Sorting algorithms and ordered containers call it for every comparison they make. More in “Essential C++ algorithms: find, sort, partition”. The std::ranges versions also take a projection: A function that a range algorithm applies to each element before comparing or testing it, such as &Student::marks in std::ranges::sort(students, {}, &Student::marks): the comparison sees two numbers, and the sort moves whole students. More in “C++ range algorithms and projections”, so a vector of records sorted by one member can be searched by that member directly. On a std::set or a std::map, call the member function lower_bound instead: the algorithm works on any iterators, but it can only step through a tree one element at a time.

Checkpoint

Check: The four searches and where they land

Question 1 of 2 The sorted marks are 35, 42, 42, 42, 58, 63, 63, 71, 88 and 95, at positions 0 to 9. What position does upper_bound(60) return?
Type a number.
Your answer position

A hint

60 is not among the marks. Where would it have to go to keep them sorted?

Show the answer: Question 1 of 2

Answer: 5 position

60 is absent, so both bounds point to where it would be inserted: position 5, the first 63. The run printed lower_bound(60) = 5 and upper_bound(60) = 5, and the empty range [5, 5) says that 60 appears 0 times.
Question 2 of 2 Typed into the figure, the values 42, 42, 42 with target 42 are found at position 1 by the classic search. What does std::lower_bound(v.begin(), v.end(), 42) return for the same vector?
Choose one answer.

Position 1, where the classic search stopped Any of the three, depending on the library Position 0, the first 42 Position 3, just past the last 42

A hint

The classic search stops at the first equal value it probes. Does lower_bound stop there too?

Show the answer: Question 2 of 2

Answer: Position 0, the first 42

A classic search answers "is it there?" and may stop at any copy. lower_bound answers "where does the run of values not less than 42 start?", so it returns position 0 here, as it returned position 1, the first of the three 42s, in the marks.

Search the answers instead of the data

Many problems ask for the smallest value that is big enough: the shortest time, the lowest capacity, the smallest budget. If you can test a candidate, and every value above a good one is also good, the candidates form a sorted range of answers to the question “is this too small?”: yes, yes, …, yes, then no for ever. partition_point finds the first no, and views::iota supplies the candidates without storing them. Here a student reads eight chapters in order, whole chapters only, and wants the smallest daily page limit that finishes them in three days:

min_pages.cpp C++ · min_pages.cpp

// Binary search on the answer: the smallest number of pages a day that finishes every chapter, in order, within
// the given number of days. partition_point searches the numbers themselves, so no array of candidates is built.
#include <algorithm>
#include <numeric>
#include <print>
#include <ranges>
#include <vector>

// Days needed to read the chapters in order, at most `limit` pages a day, whole chapters only.
int days_needed(const std::vector<int>& pages, long long limit) {
  int days = 1;
  long long today = 0;
  for (int p : pages) {
    if (today + p > limit) {  // this chapter starts a new day
      ++days;
      today = 0;
    }
    today += p;
  }
  return days;
}

int main() {
  const std::vector<int> pages{30, 12, 45, 22, 18, 40, 25, 9};
  const int days = 3;

  // Every answer lies in [largest chapter, all pages]: less than the largest chapter can never work,
  // and all pages in one day always does.
  const long long lo = std::ranges::max(pages);
  const long long hi = std::accumulate(pages.begin(), pages.end(), 0LL);

  int asked = 0;
  std::vector<long long> tested;  // every limit the search tries, in order
  // The predicate is true for limits that are too small, then false from the answer on:
  // partition_point returns the first limit for which it is false.
  auto too_small = [&](long long limit) {
    ++asked;
    tested.push_back(limit);
    return days_needed(pages, limit) > days;
  };
  const auto candidates = std::views::iota(lo, hi + 1);
  const long long best = *std::ranges::partition_point(candidates, too_small);

  std::println("limits from {} to {}: {} candidates", lo, hi, hi - lo + 1);
  std::println("smallest daily limit: {} pages, which takes {} days", best, days_needed(pages, best));
  std::println("one page less takes {} days", days_needed(pages, best - 1));
  std::print("limits tested, with the days each needs:");
  for (long long t : tested) std::print(" {} ({})", t, days_needed(pages, t));
  std::println("");
  std::println("the predicate was asked {} times; trying each limit from {} up would ask {}",
               asked, lo, best - lo + 1);
}

The smallest daily limit, with both compilers Python · min_pages_session.py

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra min_pages.cpp -o min_pages && ./min_pages
g++-16 -std=c++23 -Wall -Wextra min_pages.cpp -o min_pages-gcc && ./min_pages-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra min_pages.cpp -o min_pages && ./min_pages
limits from 45 to 201: 157 candidates
smallest daily limit: 85 pages, which takes 3 days
one page less takes 4 days
limits tested, with the days each needs: 123 (2) 84 (4) 104 (3) 94 (3) 89 (3) 87 (3) 86 (3) 85 (3)
the predicate was asked 8 times; trying each limit from 45 up would ask 41
$ g++-16 -std=c++23 -Wall -Wextra min_pages.cpp -o min_pages-gcc && ./min_pages-gcc
limits from 45 to 201: 157 candidates
smallest daily limit: 85 pages, which takes 3 days
one page less takes 4 days
limits tested, with the days each needs: 123 (2) 84 (4) 104 (3) 94 (3) 89 (3) 87 (3) 86 (3) 85 (3)
the predicate was asked 8 times; trying each limit from 45 up would ask 41

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 min_pages_session.py

The limit cannot be below the longest chapter, 45 pages, and reading all 201 pages in one day always works, so the answer lies among 157 candidates. partition_point asked the test 8 times, close to log₂ 157 ≈ 7.3, and found 85 pages: at 85 the chapters fit into three days, and at 84 they need four. Trying each limit upwards from 45 would have asked 41 times here, and the gap grows quickly: a range of a billion candidates takes 30 questions by halving. Two conditions make it correct, and both are yours to check: the test must change from yes to no exactly once along the range, and the true answer must lie inside the range you give. Step through the eight tests of the run:

Interactive · stage by stage The eight tests partition_point made to find 85 pages a day Step through the search on the 157 daily limits. Each round tests the middle limit and keeps the half that can still hold the answer.

The drawing shows the whole scene; its 10 steps are listed below.

Every step as text

157 candidates. views::iota hands partition_point the daily limits 45 to 201, 157 candidates, without storing any. The test asks of each limit it tries: is it too small, so that the chapters need more than 3 days?
Test 1: 123. The middle of 45 to 201 is 123. At 123 pages a day the chapters fit into 2 days, so 123 is not too small: the answer is 123 or below, and 124 to 201 are dropped.
Search 45 to 122. The search goes on in 45 to 122. If every one of them turns out too small, the answer is 123 itself.
Test 2: 84. The middle of 45 to 122 is 84. At 84 pages a day the chapters need 4 days: too small, and so is every limit below 84. The search goes on in 85 to 122.
Test 3: 104. 104 needs 3 days: not too small. The answer is 104 or below, so 85 to 103 are left.
Test 4: 94. 94 needs 3 days as well, so the answer is 94 or below: 85 to 93 are left.
Tests 5 and 6: 89, 87. 89 and then 87 need 3 days too. Each test halves what is left: 85 to 88, then 85 and 86.
Test 7: 86. 86 needs 3 days, so only 85 is left to test.
Test 8: 85. 85 needs 3 days, so it is not too small. No candidate is left, and every limit below 85 was shown too small by the test of 84.
85 pages a day. partition_point returns 85, the first limit that is not too small, after 8 tests, close to log₂ 157 ≈ 7.3. Trying each limit upwards from 45 would have asked 41 times.

Logarithm & Antilog Calculator Take log₂ of a range's size to see how many tests halving needs: log₂ 10⁹ is about 29.9, so 30.

Checkpoint

Check: Binary search on the answer with partition_point

Question 1 of 2 partition_point tests the limit 123 first, and at 123 pages a day the chapters fit into 2 days, so 123 is not too small. Which limits does it drop?
Choose one answer.

45 to 123 45 to 122 None until it finds a limit that needs exactly 3 days 124 to 201

Show the answer: Question 1 of 2

Answer: 124 to 201

The test is "too small?", true for small limits and false from the answer on. A false answer at 123 means the first false is at 123 or before it, so partition_point drops 124 to 201 and goes on in 45 to 122, keeping 123 as the answer if every one of those turns out too small.
Question 2 of 2 Which of these tests can std::ranges::partition_point search correctly over std::views::iota(1, 100)?
Choose one answer.

[](int x) { return x * x < 50; } [](int x) { return x % 7 != 0; } [](int x) { return x == 50; } [](int x) { return x * x > 50; }

Show the answer: Question 2 of 2

Answer: [](int x) { return x * x < 50; }

partition_point needs a test that holds for a run at the front of the range and fails for the rest. x × x < 50 changes from yes to no exactly once, at 8; the other three either start with no, or change more than once.

Five search mistakes that report no error

None of these reports an error:

Mistake	Do this instead
A comparator that does not match the sort order	A vector sorted with `std::greater<>` must be searched with `std::greater<>` too.
The algorithm on a set: `std::lower_bound` on a `std::set` makes about log₂ n comparisons, like the member function, but walks the elements one by one.	Call the member function, `s.lower_bound(x)`.
A loop that never ends: a hand-written search that keeps the middle in the range	Make the middle move, or call the library.
An overflowing middle: `(lo + hi) / 2` overflows when both are large.	`lo + (hi - lo) / 2` and `std::midpoint` do not, as the lesson on numeric algorithms shows.
A test that is not A yes-or-no test on ordered candidates is monotone when its answer changes only once along them: yes below some point and no from there on, as the test for a daily limit that is too small does.: if a candidate can be good while a larger one is bad, halving can skip the answer.	Make sure every candidate above a good one is good too.

Checkpoint

Check: Search mistakes that report no error

Question 1 of 2 s is a std::set<int>. Which call reaches the first element not less than x by walking down the tree?
Choose one answer.

std::lower_bound(s.begin(), s.end(), x) std::ranges::lower_bound(s, x) std::binary_search(s.begin(), s.end(), x) s.lower_bound(x)

Show the answer: Question 1 of 2

Answer: s.lower_bound(x)

The general algorithms work on any iterators, and on a std::set or a std::map they can only step through the elements one by one. Call the member functions of the container instead: s.lower_bound, s.upper_bound and s.equal_range.
Question 2 of 2 A hand-written search keeps int positions lo and hi, both near 2,000,000,000. Which middles stay inside int?
Choose every answer that is right.

(lo + hi) / 2 std::midpoint(lo, hi) lo + (hi - lo) / 2 (lo + hi) >> 1
Show the answer: Question 2 of 2
Answer:
- std::midpoint(lo, hi)
- lo + (hi - lo) / 2
An int stops at 2,147,483,647, so the sum lo + hi of two positions near 2,000,000,000 overflows, which is undefined behaviour for a signed type. lo + (hi - lo) / 2 and std::midpoint never compute anything larger than the bounds themselves.

Practise

Start with the idea you know least; each choice explains itself.

Binary-search bugs reproduced: wrong order, stuck loops and std::set Pro: opens with a Pro, Premium or Ultimate pass

Three mistakes cause most wrong binary searches: a search in a different order from the sort, a loop whose range stops shrinking, and the general algorithm used on a tree. Each one is reproduced below on both compilers, with the tool that catches it and the fix.

In this part:

Searching in the wrong order, and the debug mode that catches it
A loop that never ends, and the rounding that fixes it
One search on a std::set, two ways, measured
Choosing the search for each container

1 diagram · 6 runnable examples (C++, Python) · about 9 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a pass I have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Binary search on the answer, worked: proofs, paise and real numbers Pro: opens with a Pro, Premium or Ultimate pass

Binary search on the answer is only as correct as its test, so this part starts with the property the test must have and how to check it. Then it finds two answers that matter in practice, an instalment in whole paise and an interest rate as a real number, and ends with three problems to solve.

In this part:

Why the test must be monotone, with a proof for the daily limit
The smallest EMI in whole paise, checked against the formula
Real-valued answers: halving until two doubles meet
Your turn: three problems with sample tests

4 runnable examples (C header, C++, Python) · about 8 minutes

Opening this part with your pass…Pro part. It opens with the same pass as the part above.

Interview questions

Fresher · Warm-up

What is the difference between std::lower_bound and std::upper_bound, and what do they return for a value that is not in the range?

On a sorted range, lower_bound(x) returns the first element that is not less than x, and upper_bound(x) the first element that is greater than x. When x is present, lower_bound points to its first copy and upper_bound just past its last copy, so the distance between them is the number of copies, which is what equal_range returns as a pair. When x is absent, both return the same position: where x would have to be inserted to keep the range sorted, which is the end when every element is smaller. Neither says whether x was found, so compare the element with x, after checking for the end, or call binary_search for a plain yes or no.
Fresher to mid

A teammate replaced s.lower_bound(x) on a std::set with std::lower_bound(s.begin(), s.end(), x) "to use the standard algorithm". A job that ran in seconds now takes over an hour. Explain why, with the cost of one search, and say what you would change.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Fresher to mid

n print jobs with given page counts must run in order on k identical printers, each printer taking one consecutive block of jobs. Find the smallest possible number of pages on the busiest printer. Set up a binary search on the answer and show that it is correct.

Model answer, Pro. First step and follow-ups
Mid to senior

A binary search over doubles looks for a time in seconds between 0 and 10^12 and loops while hi - lo > 1e-9. It finishes on small inputs and never finishes on some large ones. Explain why, and write a loop that always ends with the most precise answer a double can give.

Model answer, Pro. First step and follow-ups

Key takeaways

lower_bound finds the first element not less than a value, upper_bound the first greater, and equal_range both.
partition_point returns the first element for which a test fails; over views::iota it searches numbers.
Binary search on the answer needs a monotone test and a range that contains the answer.
Search with the order the data was sorted by, and use the member functions of sets and maps.

References

Working Draft, Programming Languages: C++ (N4950), binary search, partitions and iota_view (ISO/IEC JTC1/SC22/WG21)
P0896R4: The One Ranges Proposal (ISO/IEC JTC1/SC22/WG21)
P0811R3: Well-behaved interpolation for numbers and pointers (ISO/IEC JTC1/SC22/WG21)
The GNU C++ Library Manual: Debug Mode (GNU Project)
The GNU C++ Library Manual: Macros (GNU Project)

Report a problem with this lesson

In this module: C++ for DSA and competitive programming

Online judge C++ compilers, flags and limits Free lesson, Pro answers: 20 minutes
A clean C++ contest template, and habits to avoid Free core, Pro depth: 8 of 20 minutes free
Fast C++ input and output for online judges Free core, Pro depth: 8 of 20 minutes free
The STL toolkit for DSA in C++ Free core, Pro depth: 8 of 20 minutes free
Custom comparators and strict weak ordering Free core, Pro depth: 8 of 20 minutes free
C++ binary search: lower_bound and partition_point Free core, Pro depth: 7 of 20 minutes free
Overflow, __int128 and modular arithmetic Free core, Pro depth: 7 of 20 minutes free
C++ unordered_map: custom hashes and anti-hash tests Free core, Pro depth: 8 of 20 minutes free
Order-statistics trees with __gnu_pbds (GCC only) Free core, Pro depth: 8 of 20 minutes free
Deep recursion, stack limits and iterative DFS Free core, Pro depth: 7 of 20 minutes free
Stress testing contest solutions in C++ Free core, Pro depth: 11 of 30 minutes free

Your country

C++ binary search: lower_bound and partition_point

What you will learn

Before you start

What you will learn

Before you start

The four searches land where a value is, or would go

Search the answers instead of the data

Five search mistakes that report no error

Practise

Binary-search bugs reproduced: wrong order, stuck loops and std::set Pro: opens with a Pro, Premium or Ultimate pass

Binary search on the answer, worked: proofs, paise and real numbers Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

What is the difference between std::lower_bound and std::upper_bound, and what do they return for a value that is not in the range?

A teammate replaced s.lower_bound(x) on a std::set with std::lower_bound(s.begin(), s.end(), x) "to use the standard algorithm". A job that ran in seconds now takes over an hour. Explain why, with the cost of one search, and say what you would change.

n print jobs with given page counts must run in order on k identical printers, each printer taking one consecutive block of jobs. Find the smallest possible number of pages on the busiest printer. Set up a binary search on the answer and show that it is correct.

A binary search over doubles looks for a time in seconds between 0 and 10^12 and loops while hi - lo > 1e-9. It finishes on small inputs and never finishes on some large ones. Explain why, and write a loop that always ends with the most precise answer a double can give.

Key takeaways

References

Related tools