Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 20m 27s17 days 22 hours 20 minutes 27 seconds.

Algorithms - Sorting and Searching · 6:13

Binary Search

We build binary search around one invariant: l always sits on a 'no', r on a 'yes', with ghost sentinels at -1 and n, and the loop runs while r - l > 1. Tracing lower_bound(9) and upper_bound(9) on [1, 3, 5, 7, 9, 9, 13, 15] gives 4 and 6, the half-open range of the two 9s. Then the classic traps (a closed-interval l = m loop that never ends and an (l + r) / 2 that overflows), partition_point and jump search, and measurements on this Mac, including why std::lower_bound on a std::set is tens of thousands of times slower than s.lower_bound.

You will learn

State the binary search invariant f(l) = 0, f(r) = 1 with sentinels l = -1 and r = n, and explain why the loop never reads them
Trace lower_bound (first >= k) and upper_bound (first > k), and use them to count and test membership
Recognise the closed-interval l = m infinite loop and the (l + r) / 2 overflow, and write l + (r - l) / 2 or std::midpoint
Use std::lower_bound, upper_bound, equal_range and partition_point correctly, and set::lower_bound for sets

Chapters

PreviousQuicksort and What std::sort Really Does NextBinary Search on the Answer