30 notes tagged
The "binary search on the answer" pattern explained: when the answer space has a monotone yes/no predicate, binary-search the answer itself. With a re...
Lower bound vs upper bound binary search explained: first index >= target vs first index > target, with ready templates in Python, Java and C++.
Random Pick with Weight (LeetCode 528): build prefix sums and binary-search a random target for O(log n) weighted sampling.
Find Right Interval (LeetCode 436): sort interval starts and binary-search the smallest start >= each interval end, O(n log n).
H-Index II (LeetCode 275): binary search on sorted citations to find the h-index in O(log n).
Guess Number Higher or Lower (LeetCode 374): classic binary search against a guess API in O(log n).
Time Based Key-Value Store (LeetCode 981): store sorted (timestamp, value) pairs per key and binary-search the latest value at or before a query time.
Count of Smaller Numbers After Self (LeetCode 315): scan right to left and binary-search each value into a sorted list to count smaller elements.
Binary search on a function: find the maximum of a unimodal function by comparing neighbouring values — a discrete alternative to ternary search.
Find the Smallest Divisor Given a Threshold (LeetCode 1283): binary search the divisor using ceiling-division sums, O(n log max).
Single Element in a Sorted Array (LeetCode 540): binary search on even indices to find the one non-duplicated element in O(log n).
Allocate Minimum Number of Pages: binary search the minimum possible maximum pages per student with a greedy allocation check, O(n log sum).