10.3 Binary search boundaries¶
10.3.1 Find the left boundary¶
Question
Given a sorted array nums of length \(n\), which may contain duplicate elements, return the index of the leftmost element target. If the element is not present in the array, return \(-1\).
Recalling the method of binary search for an insertion point, after the search is completed, the index \(i\) will point to the leftmost occurrence of target. Therefore, searching for the insertion point is essentially the same as finding the index of the leftmost target.
We can use the function for finding an insertion point to find the left boundary of target. Note that the array might not contain target, which could lead to the following two results:
- The index \(i\) of the insertion point is out of bounds.
- The element
nums[i]is not equal totarget.
In these cases, simply return \(-1\). The code is as follows:
def binary_search_left_edge(nums: list[int], target: int) -> int:
"""Binary search for the leftmost target"""
# Equivalent to finding the insertion point of target
i = binary_search_insertion(nums, target)
# Did not find target, thus return -1
if i == len(nums) or nums[i] != target:
return -1
# Found target, return index i
return i
/* Binary search for the leftmost target */
int binarySearchLeftEdge(vector<int> &nums, int target) {
// Equivalent to finding the insertion point of target
int i = binarySearchInsertion(nums, target);
// Did not find target, thus return -1
if (i == nums.size() || nums[i] != target) {
return -1;
}
// Found target, return index i
return i;
}
/* Binary search for the leftmost target */
int binarySearchLeftEdge(int[] nums, int target) {
// Equivalent to finding the insertion point of target
int i = binary_search_insertion.binarySearchInsertion(nums, target);
// Did not find target, thus return -1
if (i == nums.length || nums[i] != target) {
return -1;
}
// Found target, return index i
return i;
}
10.3.2 Find the right boundary¶
How do we find the rightmost occurrence of target? The most straightforward way is to modify the traditional binary search logic by changing how we adjust the search boundaries in the case of nums[m] == target. The code is omitted here. If you are interested, try to implement the code on your own.
Below we are going to introduce two more ingenious methods.
1. Reuse the left boundary search¶
To find the rightmost occurrence of target, we can reuse the function used for locating the leftmost target. Specifically, we transform the search for the rightmost target into a search for the leftmost target + 1.
As shown in Figure 10-7, after the search is complete, pointer \(i\) will point to the leftmost target + 1 (if exists), while pointer \(j\) will point to the rightmost occurrence of target. Therefore, returning \(j\) will give us the right boundary.
Figure 10-7 Transforming the search for the right boundary into the search for the left boundary
Note that the insertion point returned is \(i\), therefore, it should be subtracted by \(1\) to obtain \(j\):
def binary_search_right_edge(nums: list[int], target: int) -> int:
"""Binary search for the rightmost target"""
# Convert to finding the leftmost target + 1
i = binary_search_insertion(nums, target + 1)
# j points to the rightmost target, i points to the first element greater than target
j = i - 1
# Did not find target, thus return -1
if j == -1 or nums[j] != target:
return -1
# Found target, return index j
return j
/* Binary search for the rightmost target */
int binarySearchRightEdge(vector<int> &nums, int target) {
// Convert to finding the leftmost target + 1
int i = binarySearchInsertion(nums, target + 1);
// j points to the rightmost target, i points to the first element greater than target
int j = i - 1;
// Did not find target, thus return -1
if (j == -1 || nums[j] != target) {
return -1;
}
// Found target, return index j
return j;
}
/* Binary search for the rightmost target */
int binarySearchRightEdge(int[] nums, int target) {
// Convert to finding the leftmost target + 1
int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);
// j points to the rightmost target, i points to the first element greater than target
int j = i - 1;
// Did not find target, thus return -1
if (j == -1 || nums[j] != target) {
return -1;
}
// Found target, return index j
return j;
}
2. Transform into an element search¶
When the array does not contain target, \(i\) and \(j\) will eventually point to the first element greater and smaller than target respectively.
Thus, as shown in Figure 10-8, we can construct an element that does not exist in the array, to search for the left and right boundaries.
- To find the leftmost
target: it can be transformed into searching fortarget - 0.5, and return the pointer \(i\). - To find the rightmost
target: it can be transformed into searching fortarget + 0.5, and return the pointer \(j\).
Figure 10-8 Transforming the search for boundaries into the search for an element
The code is omitted here, but here are two important points to note about this approach.
- The given array
numsdoes not contain decimal, so handling equal cases is not a concern. - However, introducing decimals in this approach requires modifying the
targetvariable to a floating-point type (no change needed in Python).