Binary Search
- 2 min read
- LC-Medium
3 years ago
Template
var search = function(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
let mid = lo + Math.floor((hi - lo + 1) / 2)
if (target < nums[mid]) {
hi = mid - 1
} else {
lo = mid;
}
}
return nums[lo] == target ? lo : -1;
};
- Faaez's Tips:
- Always use
(start + end) // 2for calculating mid. There is a chance for overflow (not in Python) but this works all the time. Remember, if you're using this, your while loop needs to bestart <= end - The alternative is
start + (end - start + 1) // 2, where your while loop becomesstart < end
- Always use
Most Generalized Binary Search
Suppose we have a search space. It could be an array, a range, etc. Usually it's sorted in ascend order. For most tasks, we can transform the requirement into the following generalized form:
Minimize k , s.t. condition(k) is True
The following code is the most generalized binary search template:
def binary_search(array) -> int:
def condition(value) -> bool:
pass
left, right = 0, len(array)
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
What's really nice of this template is that, for most of the binary search problems, we only need to modify three parts after copy-pasting this template, and never need to worry about corner cases and bugs in code any more:
- Correctly initialize the boundary variables
leftandright. Only one rule: set up the boundary to include all possible elements; - Decide return value. Is it
return leftorreturn left - 1? Remember this: after exiting the while loop,leftis the minimal k satisfying theconditionfunction; - Design the
conditionfunction. This is the most difficult and most beautiful part. Needs lots of practice.
Problems
Easy
- Binary Search (LeetCode)
- First Bad Version
Medium
- Search a 2D Matrix
- Koko Eating Bananas
- Find Minimum in Rotated Sorted Array
- Search in Rotated Sorted Array
- Time Based Key-Value Store
Hard
- Median of Two Sorted Arrays