Binary Search
O(log n)Eliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
When to Use
- Searching for a target in a sorted array or matrix
- Finding the first or last occurrence of a value (boundary finding)
- Searching in a rotated sorted array
- Optimizing over a monotonic answer space (minimize maximum, maximize minimum)
Pattern Variants
Classic Sorted Array
Search for an exact target in a sorted array by comparing the midpoint and eliminating the irrelevant half.
Use for: Target exists or does not exist in sorted array, search insert position
Boundary Finding (First/Last)
Find the leftmost or rightmost position where a condition changes. Continue searching even after finding a match.
Use for: First/last occurrence, first bad version, search range, finding transition point
Rotated Array Search
At least one half is always sorted after rotation. Determine which half is sorted, then decide which half to search.
Use for: Search in rotated sorted array, find minimum in rotated array
Binary Search on Answer
When the answer itself is monotonic (if X works, X+1 also works), binary search the answer space instead of a data structure.
Use for: Koko eating bananas, capacity to ship packages, split array largest sum, minimize maximum
Interactive Visualization
Step-through visualization coming soon...
This will include beginner, intermediate, and advanced examples with code highlighting.
Practice this Pattern
Binary Search
Given a sorted array of integers and a target, return the index of the target or -1 if not found
Search Insert Position
Given a sorted array and a target, return the index if found or where it would be inserted to keep sorted order
Find First and Last Position
Given a sorted array, find the starting and ending position of a target value. Return [-1, -1] if not found
Search in Rotated Sorted Array
A sorted array has been rotated at some pivot. Search for a 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
Find Peak Element
Find any element that is strictly greater than its neighbors. nums[-1] = nums[n] = -infinity
First Bad Version
Given a version control system where all versions after a bad version are bad, find the first bad version
Search in Rotated Sorted Array II
Search a target in a rotated sorted array that may include duplicates
Peak Index in Mountain Array
Find the index of the peak element in a mountain array (strictly increasing then decreasing)
Find the Smallest Divisor Given a Threshold
Find the smallest divisor such that sum of ceil(nums[i]/divisor) is within threshold
Minimum Number of Days to Make m Bouquets
Pick m bouquets of k adjacent blooms, minimizing flowering day
Magnetic Force Between Two Balls
Place m balls in baskets to maximize minimum distance
Search a 2D Matrix II
Search for a target in a sorted matrix where each row and each column is sorted ascending
Koko Eating Bananas
Koko can eat bananas at speed k per hour. Given piles and h hours, find the minimum k to eat all bananas in time
Capacity To Ship Packages
Find the least weight capacity of a ship so that all packages can be shipped within d days (packages must stay in order)
Search a 2D Matrix
Search for a target in a matrix where each row is sorted and first element of each row is greater than last element of previous row
Split Array Largest Sum
Split an array into k non-empty continuous subarrays to minimize the largest subarray sum
Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log(min(m,n))) time