Modified Binary Search
Classic binary search adapted: search in rotated arrays, answer-space binary search, or find a boundary condition instead of an exact match.
Time
O(log n)
Space
O(1)
Recognize it when
- Sorted or rotated sorted array
- "Find minimum/maximum X such that condition holds" — search the answer space
- Find left/right boundary of a range
Questions — ordered by difficulty
Binary Search
Given a sorted array and a target, return the index of the target or -1.
Search in Rotated Sorted Array
Search a target in a sorted array that has been rotated at some unknown pivot.
Find Minimum in Rotated Sorted Array
Find the minimum element in a rotated sorted array.
Koko Eating Bananas
Find the minimum eating speed k such that Koko can eat all bananas in h hours.
Median of Two Sorted Arrays
Find the median of two sorted arrays in O(log(m+n)) time.
Search a 2D Matrix
Search for a target in an m×n matrix where each row is sorted and the first integer of each row > last integer of previous row.
Find Peak Element
A peak element is one that is strictly greater than its neighbors. Find any peak in O(log n).
Split Array Largest Sum
Split an array into k non-empty subarrays to minimize the largest subarray sum.
Kth Smallest Element in a Sorted Matrix
Find the kth smallest element in an n×n matrix where each row and column is sorted.