3 min read
Binary Search Done Correctly: Invariants Over Memorization
The template everyone thinks they know — invariant included. Python solution and complexity analysis for the modified binary search interview pattern.
Tag
Binary Search
Articles tagged Binary Search on The Augmented Dev.
11 articles
3 min read
Capacity to Ship Packages: The Same Search, New Costume
Minimum ship capacity via a greedy day-splitting check. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Find First and Last Position With Two Boundary Searches
Range of a duplicated target via lower and upper bound in O(log n). Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Find Minimum in Rotated Sorted Array: Hunting the Seam
Converge on the rotation seam via right-edge comparison. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Find Peak Element: Binary Search Without Sorted Input
Climb the slope — halving works even on unsorted data. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Koko Eating Bananas: Minimize a Feasible Rate
Search on eating speed with a ceiling-division check. Python solution and complexity analysis for the modified binary search interview pattern.
4 min read
Median of Two Sorted Arrays: The Partition Search
The O(log min(m, n)) partition argument, demystified. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Search a 2D Matrix as One Flattened Sorted Array
One binary search over rows*cols with divmod index mapping. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Search Insert Position and the Lower Bound Idiom
The lower_bound boundary template every variant builds on. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Search in Rotated Sorted Array: One Half Is Always Sorted
The rotated classic — decide which half is sorted, then range-check. Python solution and complexity analysis for the modified binary search interview pattern.
3 min read
Integer Square Root: Search the Answer Space
First search-on-the-answer: largest k with k*k at most x. Python solution and complexity analysis for the modified binary search interview pattern.