实际二分搜索时的思维框架
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 1011. Capacity To Ship Packages Within D Days | 🟠 |
| 410. Split Array Largest Sum | 🔴 |
| 875. Koko Eating Bananas | 🟠 |
In Binary Search Framework Explained, we delved into the details of binary search, discussing the three scenarios: "searching for an element," "searching for the left boundary," and "searching for the right boundary." This teaches you how to write a bug-free binary search algorithm.
However, the binary search code framework summarized in the previous article is limited to the basic scenario of "searching for a specific element in a sorted array." Real algorithm problems are not always so straightforward, and you might find it hard to recognize that binary search can be applied.
Therefore, this article aims to provide a systematic framework for applying binary search algorithms. It will help you think and analyze methodically when encountering binary search-related problems in practice, allowing you to solve them step by step.
Basic Binary Search Code
Binary search is fundamentally about searching for an element target in a sorted array and returning the index of that element.
If the element doesn't exist, you can return a special value. These kinds of details can be easily adjusted in the algorithm implementation.
Another important issue is when there are multiple occurrences of target in the sorted array. These elements will be adjacent. This raises the question of whether the algorithm should return the index of the leftmost target or the rightmost target, known as "searching for the left boundary" and "searching for the right boundary." This can also be achieved by tweaking the algorithm code.
We discussed these issues in detail in our previous article Binary Search Core Framework. Readers who are not clear about this are advised to review the previous article. Those who already understand the basic binary search algorithm can continue reading.
In specific algorithm problems, the common scenarios are 'searching for the left boundary' and 'searching for the right boundary.' It's rare to be asked to 'search for a single element' alone.
This is because algorithm problems often require finding the extreme values, such as the 'minimum speed' for eating bananas or the 'minimum carrying capacity' of a ship. The process of finding these extreme values inherently involves searching for a boundary. Therefore, we will delve into the detailed analysis of these two boundary search binary algorithm codes.
注
Note: In this article, I use the left-closed, right-open binary search approach. If you are accustomed to the closed interval approach, you can modify the code accordingly.
The specific code implementation for the binary search algorithm that searches for the left boundary is as follows:
// search for the left boundary
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// when target is found, shrink the right boundary
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}// search for the left boundary
int left_bound(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// when target is found, shrink the right boundary
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
}def left_bound(nums: List[int], target: int) -> int:
# search for the left boundary
if len(nums) == 0:
return -1
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] == target:
# when target is found, shrink the right boundary
right = mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left// Search for the left boundary
func left_bound(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left, right := 0, len(nums)
for left < right {
mid := left + (right - left) / 2
if nums[mid] == target {
// When target is found, shrink the right boundary
right = mid
} else if nums[mid] < target {
left = mid + 1
} else if nums[mid] > target {
right = mid
}
}
return left
}// search for the left boundary
var left_bound = function(nums, target) {
if (nums.length === 0) return -1;
let left = 0, right = nums.length;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
// when target is found, shrink the right boundary
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left;
};Suppose the input array is nums = [1,2,3,3,3,5,7] and the element we want to search for is target = 3. The algorithm will return the index 2.
If we draw a diagram, it looks like this:
The specific code implementation for the binary search algorithm to "search the right boundary" is as follows:
// search for the right boundary
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// when target is found, shrink the left boundary
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1;
}// search for the right boundary
int right_bound(vector<int>& nums, int target) {
if (nums.size() == 0) return -1;
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// when target is found, shrink the left boundary
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1;
}# Search for the right boundary
def right_bound(nums: list[int], target: int) -> int:
if len(nums) == 0:
return -1
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] == target:
# When target is found, shrink the left boundary
left = mid + 1
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid
return left - 1// Search for the right boundary
func right_bound(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] == target {
// When target is found, shrink the left boundary
left = mid + 1
} else if nums[mid] < target {
left = mid + 1
} else if nums[mid] > target {
right = mid
}
}
return left - 1
}// search for the right boundary
var right_bound = function(nums, target) {
if (nums.length === 0) return -1;
let left = 0, right = nums.length;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
// when target is found, shrink the left boundary
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1;
};Given the same input as above, the algorithm will return the index 4. If we draw a diagram, it looks like this:
Alright, the above content is a review, and I believe readers who have reached this point should understand it. Remember the above image; any problem that can be abstracted into this image can be solved using binary search.