Skip to main content

Courses About Pricing Educators

Sign in Get started

Courses About Pricing Educators

Get started Sign in

Loading courses

Loading lessons

Binary Search: Data Structures and Algorithms: Uncharted

Courses Data Structures and AlgorithmsBinary Search

Binary SearchPro

Narrow ordered intervals, find duplicate bounds, and search monotone answer spaces.

Data Structures and Algorithms
Unit 8 of 16
20 lessons
130 min
420 XP

This unit is part of Pro. Upgrade to open every lesson in it.

Lessons

20 total

1The Phonebook GameUse sorted order and a midpoint comparison to eliminate one impossible half of a search interval.ProInteractiveConcept6 min20 XPOpen
2lo, hi, midApply inclusive lo-hi binary-search loop to finding an exact value inside an inclusive sorted interval.ProCodeConcept6 min20 XPOpen
3Count the HalvingsApply binary-search logarithmic probe counter to measuring probes for ranges of size 16 and 1024.ProCodeConcept6 min20 XPOpen
4Off-by-One ClinicApply strictly shrinking inclusive binary-search bounds to repairing bounds so every unsuccessful round strictly shrinks the interval.ProCodeConcept6 min20 XPOpen
5Predict lo and hiUpdate inclusive lo and hi bounds correctly after recording a binary-search midpoint comparison.ProInteractiveConcept6 min20 XPOpen
6First OccurrenceApply left-biased match search to continuing left after finding a duplicate target.ProCodeConcept6 min20 XPOpen
7Last OccurrenceApply paired leftmost and rightmost bound searches to combining the two duplicate bounds into an occurrence count.ProCodeConcept6 min20 XPOpen
8Insert PositionApply lower-bound insertion search to hand-building the first slot whose value is not smaller than the target before comparing Python bisect_left.ProCodeConcept6 min20 XPOpen
9Search a RangeApply two-bound inclusive range search to returning the inclusive span formed by left and right bounds.ProCodePractice8 min20 XPOpen
10The Answer Is a NumberApply binary search over a monotone feasible capacity to finding the smallest daily capacity whose schedule is feasible.ProCodeConcept6 min20 XPOpen
11Square Roots by HalvingApply largest-true integer predicate search to finding the largest integer whose square does not exceed the input.ProCodeConcept6 min20 XPOpen
12The Predicate LineLocate a false-to-true transition by maintaining the feasible side of a monotone predicate.ProInteractiveConcept6 min20 XPOpen
13The Rotated ShelfApply binary search with one sorted rotated half to identifying the sorted half of a rotated alphabetized shelf.ProCodeConcept6 min20 XPOpen
14Peak FindingApply binary search along the rising or falling slope to following the rising slope toward a local peak.ProCodeConcept6 min20 XPOpen
15Beat the BudgetApply opaque compare callback with a logarithmic call budget to calling an opaque compare function within a logarithmic budget.ProCodePractice8 min20 XPOpen
16First Bad VersionApply first-true API predicate search to finding the first failing release through a good-or-bad API.ProCodePractice8 min20 XPOpen
17When Sorted LiesReject binary search when ordering or monotonicity does not justify discarding a half.ProInteractiveConcept6 min20 XPOpen
18Bounds in the WildRecognize capacity and threshold problems that support binary search over a monotone feasibility test.ProInteractiveConcept6 min20 XPOpen
19Explain the InvariantState and preserve the binary-search candidate-interval invariant through termination.ProInteractiveConcept6 min20 XPOpen
20Binary Search Mastery CheckApply lower and upper bound mastery synthesis to deriving first, last, and insertion bounds from two monotone searches.ProCodeMastery check10 min40 XPOpen