Binary Search Templates
binary-search-templates
Algorithms
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.
Not Started
0%
Code Snippets
Python Binary Search Template
Binary search runs in O(log n) over any sorted array, but the off-by-one variations bite everyone. This entry ships three runnable templates: the equality search, the lower-bound (`bisect_left`) variant, and the upper-bound (`bisect_right`) variant. Each one handles every edge case the test list throws at it.
std::lower_bound Recipes
`std::lower_bound` returns an iterator to the first element NOT less than a target in a sorted range, while `std::upper_bound` returns the first element strictly greater. This snippet shows how to use both for sorted-insertion, range-counting, and predicate-based binary search via the comparator overload. All run in O(log n) on random-access iterators.
Question Banks
Binary Search Fundamentals
Lower bound, upper bound, and the off-by-one corners of classic binary search. Code stems are Python.
Binary Search on the Answer
Cast feasibility problems as binary search over a monotone predicate. Drills cover min capacity, max chunk, and the standard template.