Algorithms
Binary Search Templates
Difficulty: Intermediate
Standard binary search returns an arbitrary index of a target if duplicates exist, but real problems usually want the first such index, the last such index, or the smallest capacity that ships every package within D days. Each variation...
Binary Search Templates
Standard binary search returns an arbitrary index of a target if duplicates exist, but real problems usually want the first such index, the last such index, or the smallest capacity that ships every package within D days. Each variation needs a slightly different loop condition and return value, and getting one wrong produces an off-by-one bug or an infinite loop.
Binary Search Templates turns those variations into a small set of memorable templates. You will work through first and last occurrence with <= versus < loop conditions, lower bound and upper bound (the templates behind Python's bisect_left and bisect_right), binary search on the answer space (the "minimize the maximum" pattern that solves Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum), and search in rotated sorted arrays where the invariant holds for exactly one half at each step.
In Binary Search (Intro), you wrote the canonical exact-match loop and learned why it is O(log n). This lesson keeps the halving idea but switches the question from "is target here?" to "what is the smallest index that satisfies a monotonic predicate?".
Next, Linked List Algorithms turns to pointer manipulation patterns.
Prerequisites:
Binary Search (Intro)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement binary search templates for first and last occurrence of a target.
Use lower bound and upper bound to find insertion points in sorted arrays.
Apply binary search on the answer space to solve optimization problems with monotonic predicates.
Search in a rotated sorted array by identifying which half is sorted.
Debug common binary search errors including off-by-one mistakes and infinite loops.
Choose the correct binary search template for a given problem type.
Why This Matters
01
Binary search variations are among the most common medium-difficulty interview questions at top companies.
02
The 'binary search on answer space' pattern solves an entire class of optimization problems: minimize the maximum, maximize the minimum.
03
Understanding lower bound and upper bound unlocks Python's bisect module and C++'s std::lower_bound, which are essential library functions.
04
Rotated array search tests deep understanding of invariants and is a classic interview favorite.
Key Terms
6 terms you'll encounter in this lesson
Lower bound
The first position where a target could be inserted without breaking sorted order. Equivalent to the index of the first element >= target.
Upper bound
The first position after all occurrences of the target. Equivalent to the index of the first element > target.
Monotonic predicate
A boolean function that transitions from false to true (or true to false) exactly once as the input increases. Binary search on answer space requires this property.
Answer space
The range of possible answers to an optimization problem. Binary search narrows this range by testing the midpoint with a feasibility check.
Rotated sorted array
A sorted array that has been rotated: the last k elements are moved to the front. Example: [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated by 4.
Pivot point
In a rotated array, the index where the rotation occurred — the smallest element. Also called the rotation point.
Heads Up
Common misconceptions to watch out for
"Binary search only works for finding exact matches"
Binary search can find first/last occurrences, insertion points, and even optimize over an answer space. The key requirement is a monotonic property that lets you eliminate half the search space.
"left < right and left <= right are interchangeable"
They produce different behaviors. With left <= right, the loop runs when left == right (checking one element). With left < right, it stops when left == right (the answer is at left). Choose based on your template.
"Binary search on answer space requires a sorted array"
Binary search on answer space does not search an array at all. It searches a range of possible answers [lo, hi] and uses a feasibility function to decide which half to eliminate. The feasibility function must be monotonic.