Binary Search in Action
This article will resolve
| 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
The essence of binary search is to search for an element target in a sorted array and return the index corresponding to that element.
If the element does not exist, a special value can be returned. Such details can be easily adjusted in the algorithm implementation.
Another important consideration is when multiple instances of target exist in the sorted array. These instances 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 on this are advised to review the previous article. Those who understand the basic binary search algorithm can continue reading.
In specific algorithm problems, the scenarios commonly used are "searching for the left boundary" and "searching for the right boundary." Rarely are you asked to "search for a single element."
This is because algorithm problems often require finding extremums, such as the "minimum speed" for eating bananas or the "minimum carrying capacity" of a ship. The process of finding extremums inherently involves searching for a boundary. Therefore, we will delve into the detailed analysis of these two binary search algorithms for boundary searching.
Note
Note that 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 to "search 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 you want to search for is target = 3. The algorithm will return index 2.
If you draw a diagram, it looks like this:
Here is the specific code implementation of the "searching for the right boundary" binary search algorithm:
// 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;
};With the input as mentioned above, the algorithm will return index 4. If we draw a diagram, it looks like this:
Good, the content above serves as a review. Readers who have reached this point should understand it. Remember the image above; any problem that can be abstracted into this image can be solved using binary search.