Binary Search
binary-search
Algorithms
Binary Search (Intro)
Searching a sorted array of one billion elements with linear search takes up to a billion comparisons. Binary search needs about thirty. The same input, the same hardware, two algorithms with completely different scaling behavior, separated only by the assumption that the array is sorted. **Binary Search (Intro)** explains how to get that speedup and how to write the algorithm without the off-by-one errors and infinite loops that trip up almost everyone the first time. You will implement the canonical two-pointer template with `left` and `right` indices, learn why `mid = left + (right - left) / 2` matters for avoiding integer overflow, and trace the algorithm step by step on small inputs to see the search space halve each iteration. The lesson also surveys built-in support across languages (`Array.indexOf` is _not_ a binary search; Python's `bisect` is) and the most common pitfalls. In **Arrays & Strings**, you saw why indexed access on an array is `O(1)`; binary search is the first algorithm that uses that property to skip past whole regions instead of walking through them. **Big-O Notation (Upper Bound)** gave you the language `O(log n)` and the reasoning that explains why halving leads to logarithmic growth. From here you will move into **Two Pointers (Intro)**, which generalizes the same coordinated-index idea beyond exact-match searching.
Not Started
0%
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%
Practice Problems
Binary Search
Given a sorted array of integers and a target value, return the index of the target using binary search, or -1 if not found.
Count Complete Tree Nodes
Given the root of a complete binary tree, return the number of nodes in the tree.
First Bad Version
Given n versions numbered 1 to n and an API that tells whether a version is bad, find the first bad version using minimum API calls.
Search Insert Position
Given a sorted array and a target value, return the index where the target is found or where it would be inserted to keep the array sorted.
Maximum Profit in Job Scheduling
Given jobs with start times, end times, and profits, find the maximum profit you can earn by scheduling non-overlapping jobs.
Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log(min(m, n))) time by binary searching for the correct partition.
Swim in Rising Water
Given an n x n grid of elevations, find the minimum time t at which you can swim from the top-left to the bottom-right corner.
Find First and Last Position of Element in Sorted Array
Given a sorted array and a target, find the starting and ending position of the target value in O(log n) time.
Find Minimum in Rotated Sorted Array
Find the minimum element in a sorted array that has been rotated between 1 and n times, using O(log n) time.
Find Peak Element
Find a peak element in an array where the element is strictly greater than its neighbors. Return any peak's index in O(log n) time.
Koko Eating Bananas
Find the minimum eating speed at which Koko can finish all banana piles within h hours, using binary search on the answer.
Longest Increasing Subsequence
Given an integer array, return the length of the longest strictly increasing subsequence.
Search a 2D Matrix II
Search for a target value in an m x n matrix where each row and each column is sorted in ascending order, using an efficient staircase approach.
Search a 2D Matrix
Write an efficient algorithm to search for a target value in an m x n matrix where each row is sorted and the first integer of each row is greater than the last integer of the previous row.
Search in Rotated Sorted Array
Search for a target value in a rotated sorted array of unique integers, returning its index or -1 if not found, in O(log n) time.
Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. Use binary search to achieve O(log x) time without using built-in exponent functions.
Time Based Key-Value Store
Design a key-value store that can store multiple values for the same key at different timestamps and retrieve the value at a given timestamp using binary search.
Two Sum II - Input Array Is Sorted
Given a 1-indexed sorted array, find two numbers that add up to a target and return their indices.
Code Snippets
Binary Search Template
Binary search is the most asked algorithm in interviews and the easiest to get wrong: off-by-one bugs, infinite loops, integer overflow on the midpoint. This snippet covers the iterative bounds template that always terminates, a recursive variant for contrast, and a found-or-insertion-point version that returns where the value would go if absent. The same skeleton powers the lower-bound and upper-bound variants in the next entry.
Lower-Bound and Upper-Bound Binary Search
Lower-bound and upper-bound binary search are the two primitives every other range query depends on. Lower-bound returns the first index where a value could be inserted; upper-bound returns the first index strictly greater than the value. This snippet covers both forms, then composes them to count occurrences in a sorted array in O(log n).
bisect for Sorted-List Insertion
The `bisect` module is Python's binary-search-on-a-list primitive: `bisect_left` and `bisect_right` find the insertion index for a value in a sorted list in O(log n). This snippet covers the basic insertion-point query, the `insort` shortcut for keeping a list sorted as you build it, and the count-occurrences and rank-percentile recipes that fall out for free.
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.
Community
bisect Instead of sort() on Every Insert (Python)
I had a leaderboard insert loop running list.append + list.sort. Swapping to bisect.insort cut the loop from 4.2s to 0.14s on 50k inserts. The 5-line rewrite plus the keyed variant is here.
Split Array Largest Sum
Split a non-negative integer array into k contiguous parts that minimize the maximum part sum, via binary search on the answer plus a greedy feasibility check.
Find Smallest Letter Greater Than Target
Classic upper_bound on a sorted character array, with a wrap-around twist that makes the binary-search invariants worth thinking through carefully.
Arranging Coins
Find the largest k such that 1+2+...+k <= n, framed as a binary-search-on-answer warmup with a closed-form sanity check.
Snapshot Array
Implement an array-like structure with constant-time set / snap and binary-search get-at-snapshot, using per-index version lists.
Capacity to Ship Packages Within D Days
Binary-search-on-answer for the smallest belt capacity that ships all packages in order within D days, with a linear feasibility check per candidate.
Find K Closest Elements
Find a length-k window in a sorted array whose elements are closest to x, using a binary search on the LEFT edge of the window.
Binary Search on the Answer Space
I had to bin-pack 5M jobs across N machines under a wall-time budget; sort-and-greedy timed out. The fix was binary searching the makespan: a `feasible(m)` predicate plus the standard lo/hi loop turns an NP-hard scheduler into O(N log range).
Binary Search Questions I Overcomplicated
Four binary search problems I made harder than they needed to be. Each shows the version I wrote in the loop and the version that should have been my first instinct, with invariants written down.
Binary Search: Divide and Conquer
The template you actually need, three variations that cover most interview problems, and the off-by-one bug that catches every engineer at least once.
Random Pick With Weight
Sample an index proportional to a positive-integer weight using a prefix-sum array and binary search.