Unit 2.3 · about 5 h
98 / 324Binary search: intervals, bounds and feasibility predicates
Binary search fails in production through boundary bugs, not through asymptotics. One invariant derives every variant, and the same invariant searches answer spaces that are not arrays at all.
- derive
- implement
You can now
- Prove the binary-search loop invariant and derive safe boundary updates for lower-bound, upper-bound and first-true variants.
- Implement exact-match, lower-bound, upper-bound and answer-space search from the invariant, with differential tests against
bisect. - Turn a monotone feasibility predicate into
lo/hibounds with cost \(O(F \log W)\), and defend why monotonicity (not sortedness) is the requirement.
Covers
- Binary-search interval conventions and termination
- Lower bound, upper bound and duplicate handling
- Binary search on a monotone feasibility predicate
Study, in this order
4 steps
- Binary search: the canonical versionDSA Handbook - search, trees and heaps
Pick the template from the question, not the input; Template A: exact-match on a closed interval; Template B: lower-bound on a half-open interval; Template C: predicate-driven leftmost; The off-by-one death zone
- Binary search variants: `lower_bound`, `upper_bound`, peaks, and rotated arraysDSA Handbook - search, trees and heaps
Variant 1:
lower_boundandupper_boundon duplicates; Variant 4: binary search on the answer; PitfallsDepth · Skim Variants 2, 3 and 5 (rotated arrays, peaks, cross-array partition) for recognition only; they are not implemented here.
- Lecture Note 12: the dictionary lower boundAlgorithms
Section 12.3 Information Theory
Depth · Read only the dictionary lower-bound argument (Omega(log n) queries); the sorting sections belong to the merge-sort unit.
- Algorithmica: Binary SearchAlgorithmica - search and sorting performance
Binary Search (The Bottleneck); Removing Branches
Depth · Read for the branch-prediction and cache explanation only. Every speedup number there (2.5x to 3x branchless on small arrays, about 2x Eytzinger against
std::lower_bound) is a C++ measurement with Clang 10 on Zen 2; do not transfer any crossover point to Python.
Focus on
- Closed
[lo,hi]pairs withwhile lo <= hiandhi=mid-1; half-open[lo,hi)pairs withwhile lo < hiandhi=mid. Mixing the pairs is the non-termination bug. lower_boundkeeps equality right withnums[mid] < target;upper_boundkeeps equality left withnums[mid] <= target. Their difference counts duplicates.- Answer-space search is Template C with a monotone predicate: feasibility must hold above (or below) a threshold with no gaps. Cost is \(O(F \log W)\) for predicate cost \(F\) and width \(W\).
- Algorithmica's C++ numbers explain why equal-asymptotic searches cross over (an unpredictable branch costs 10 to 15 cycles, a cache miss up to 300), but Python's interpreter overhead moves every crossover. Verify bounds against
bisect, not against ported constants.
Reproduce closed-book
lower_bound, upper_bound and a first-true search on [lo,hi). On [1,2,2,2,3] with target 2, return 1 and 4. Reproduce Koko: piles [3,6,7,11] with h=8 must return 4. Run a Hypothesis differential test of both bounds against bisect_left and bisect_right on 300 sorted lists up to length 30.Traps
- Returning
lofor every template. The upper-bound twin and Template A need their own return values; derive each from the invariant instead of memorizing one. - Writing
lo=midorhi=midin Template A after a miss. The closed interval needsmid+1andmid-1to shrink; the half-open forms are the ones that keepmid. - Searching on a predicate that is not monotone. Prove
hours(k)is nonincreasing in \(k\) (or your predicate's direction) before trusting the loop; a gap in feasibility silently returns a wrong answer.
Practice
LeetCode 875: Koko Eating Bananas
Solve with a monotone hours predicate on [1, max(piles)]; example piles [3,6,7,11] with h=8 expects 4
Attempt cold: state the predicate and its monotonicity before coding. After submitting, read the AlgoMaster write-up for Koko Eating Bananas (https://algomaster.io/learn/dsa/koko-eating-bananas).
LeetCode 34: Find First and Last Position of Element in Sorted Array
Two bound searches; example inputs ([5,7,7,8,8,10], 8) expects [3,4] and ([5,7,7,8,8,10], 6) expects [-1,-1]
Cover the empty array and the absent target without extra branches. After submitting, read the AlgoMaster write-up for Find First and Last Position of Element in Sorted Array (https://algomaster.io/learn/dsa/find-first-and-last-position-of-element-in-sorted-array).
Self-test
-
Prove Template B terminates with lo at the lower bound.
Invariant: every indexj < lohasnums[j] < targetand every indexk >= hihasnums[k] >= target. Each iteration replaces[lo,hi)with a strictly smaller interval that preserves the invariant, sincemidsits strictly insidewhile lo < hi. The width reaches zero, solo == hi, and the invariant says every index belowlois < target and every index fromloon is >= target (lo = nwhen none is), solois the lower bound. -
On
[1,2,2,2,3], what do exact-match search,lower_boundandupper_boundreturn for target 2, and why?Exact match returns some index in{1,2,3}.lower_boundreturns 1 because the strict comparison keeps equality right;upper_boundreturns 4 because the non-strict comparison keeps equality left. The duplicate count is \(4 - 1 = 3\). -
Why is binary search correct on the Koko predicate when speeds are not stored in an array?
hours(k)is nonincreasing in \(k\): a faster speed never needs more hours. That monotonicity is the only requirement; the loop searches the predicate, not a sorted array. Each probe scans \(n\) piles, so the cost is \(O(n \log \max(\text{piles}))\). -
A colleague ports Algorithmica's branchless binary search to Python expecting 2.5x. What do you tell them?
The 2.5x to 3x number is Algorithmica's C++ measurement (Clang 10, Zen 2) on small arrays. Python's per-iteration interpreter overhead dominates and removes the branch-prediction effect, so the constant does not transfer. Measure withtimeiton the real workload instead.
Completion criterion
Stop when
Your three searches match bisect on 300 random cases, Koko returns 4, and you can write any bound variant from its invariant without trial edits.
Leads to
- 2.5 Binary search trees, balance and augmented trees Ordered search moves from static arrays to dynamic trees.
- 2.8 Interval ordering, merging and sweep lines Sorted order plus boundary discipline returns in interval merging.
Comes after
- 1.8 Prefix sums, difference arrays and prefix plus hashPrefix sums plus binary search answer constrained-rectangle queries.
Resources for this unit
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
Also in this section
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.