10.3 二分查找边界¶
10.3.1 查找左边界¶
Question
给定一个长度为 \(n\) 的有序数组 nums ,其中可能包含重复元素。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素,则返回 \(-1\) 。
回忆二分查找插入点的方法,搜索完成后 \(i\) 指向最左一个 target ,因此查找插入点本质上是在查找最左一个 target 的索引。
考虑通过查找插入点的函数实现查找左边界。请注意,数组中可能不包含 target ,这种情况可能导致以下两种结果。
- 插入点的索引 \(i\) 越界。
- 元素
nums[i]与target不相等。
当遇到以上两种情况时,直接返回 \(-1\) 即可。代码如下所示:
/* 二分查找最左一个 target */
function binarySearchLeftEdge(nums: Array<number>, target: number): number {
// 等价于查找 target 的插入点
const i = binarySearchInsertion(nums, target);
// 未找到 target ,返回 -1
if (i === nums.length || nums[i] !== target) {
return -1;
}
// 找到 target ,返回索引 i
return i;
}
可视化运行
10.3.2 查找右边界¶
那么如何查找最右一个 target 呢?最直接的方式是修改代码,替换在 nums[m] == target 情况下的指针收缩操作。代码在此省略,有兴趣的读者可以自行实现。
下面我们介绍两种更加取巧的方法。
1. 复用查找左边界¶
实际上,我们可以利用查找最左元素的函数来查找最右元素,具体方法为:将查找最右一个 target 转化为查找最左一个 target + 1。
如图 10-7 所示,查找完成后,指针 \(i\) 指向最左一个 target + 1(如果存在),而 \(j\) 指向最右一个 target ,因此返回 \(j\) 即可。
图 10-7 将查找右边界转化为查找左边界
图解 10-7:用插入点查找右边界
在有序整数数组中,用 target + 1 的插入点减 1 得到右边界候选索引;返回前须确认索引有效且对应元素等于 target。
有序整数数组为 nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15],目标元素 target = 6;其中索引 2 至 6 为五个连续的 6。画面同时标出查找左边界与查找右边界结束时的两组双指针状态。
左侧直接执行“查找最左一个 target”:二分插入点搜索结束时,指针 i 停在索引 2(首个 6,青色方格),指针 j 停在索引 1(值为 3),因此 6 的左边界即为 i = 2。
右侧展示“查找最右一个 target”与“查找最左一个 target + 1”之间的双向“等价”转化:对 target + 1 = 7 执行二分查找插入点,搜索结束时指针 i 指向首个大于等于 7 的元素(即索引 7 的值 10),而指针 j = i − 1 恰好指向索引 6 的最后一个 6(青色方格)。注意数组中并不存在元素 7,图中的“查找最左一个 target + 1”是指调用二分插入点函数求 7 的左边界插入位置 i = 7,而非直接命中元素 7。
这一等价转化利用了数组元素皆为整数的性质:数组中大于 6 的元素都大于等于 7,因此首个大于等于 7 的位置就是首个大于 6 的位置。在实际代码中得到 j = i − 1 后,还需检查 j 是否未越界且 nums[j] == target,若不满足则说明数组中不存在 target,应返回 −1。
请注意,返回的插入点是 \(i\) ,因此需要将其减 \(1\) ,从而获得 \(j\) :
def binary_search_right_edge(nums: list[int], target: int) -> int:
"""二分查找最右一个 target"""
# 转化为查找最左一个 target + 1
i = binary_search_insertion(nums, target + 1)
# j 指向最右一个 target ,i 指向首个大于 target 的元素
j = i - 1
# 未找到 target ,返回 -1
if j == -1 or nums[j] != target:
return -1
# 找到 target ,返回索引 j
return j
/* 二分查找最右一个 target */
int binarySearchRightEdge(vector<int> &nums, int target) {
// 转化为查找最左一个 target + 1
int i = binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
int binarySearchRightEdge(int[] nums, int target) {
// 转化为查找最左一个 target + 1
int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
int BinarySearchRightEdge(int[] nums, int target) {
// 转化为查找最左一个 target + 1
int i = binary_search_insertion.BinarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
func binarySearchRightEdge(nums []int, target int) int {
// 转化为查找最左一个 target + 1
i := binarySearchInsertion(nums, target+1)
// j 指向最右一个 target ,i 指向首个大于 target 的元素
j := i - 1
// 未找到 target ,返回 -1
if j == -1 || nums[j] != target {
return -1
}
// 找到 target ,返回索引 j
return j
}
/* 二分查找最右一个 target */
func binarySearchRightEdge(nums: [Int], target: Int) -> Int {
// 转化为查找最左一个 target + 1
let i = binarySearchInsertion(nums: nums, target: target + 1)
// j 指向最右一个 target ,i 指向首个大于 target 的元素
let j = i - 1
// 未找到 target ,返回 -1
if j == -1 || nums[j] != target {
return -1
}
// 找到 target ,返回索引 j
return j
}
/* 二分查找最右一个 target */
function binarySearchRightEdge(nums, target) {
// 转化为查找最左一个 target + 1
const i = binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
const j = i - 1;
// 未找到 target ,返回 -1
if (j === -1 || nums[j] !== target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
function binarySearchRightEdge(nums: Array<number>, target: number): number {
// 转化为查找最左一个 target + 1
const i = binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
const j = i - 1;
// 未找到 target ,返回 -1
if (j === -1 || nums[j] !== target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
int binarySearchRightEdge(List<int> nums, int target) {
// 转化为查找最左一个 target + 1
int i = binarySearchInsertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
fn binary_search_right_edge(nums: &[i32], target: i32) -> i32 {
// 转化为查找最左一个 target + 1
let i = binary_search_insertion(nums, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
let j = i - 1;
// 未找到 target ,返回 -1
if j == -1 || nums[j as usize] != target {
return -1;
}
// 找到 target ,返回索引 j
j
}
/* 二分查找最右一个 target */
int binarySearchRightEdge(int *nums, int numSize, int target) {
// 转化为查找最左一个 target + 1
int i = binarySearchInsertion(nums, numSize, target + 1);
// j 指向最右一个 target ,i 指向首个大于 target 的元素
int j = i - 1;
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1;
}
// 找到 target ,返回索引 j
return j;
}
/* 二分查找最右一个 target */
fun binarySearchRightEdge(nums: IntArray, target: Int): Int {
// 转化为查找最左一个 target + 1
val i = binarySearchInsertion(nums, target + 1)
// j 指向最右一个 target ,i 指向首个大于 target 的元素
val j = i - 1
// 未找到 target ,返回 -1
if (j == -1 || nums[j] != target) {
return -1
}
// 找到 target ,返回索引 j
return j
}
可视化运行
2. 转化为查找元素¶
我们知道,当数组不包含 target 时,最终 \(i\) 和 \(j\) 会分别指向首个大于 target 的元素和最右一个小于 target 的元素。
因此,如图 10-8 所示,我们可以构造一个数组中不存在的元素,用于查找左右边界。
- 查找最左一个
target:可以转化为查找target - 0.5,并返回指针 \(i\) 。 - 查找最右一个
target:可以转化为查找target + 0.5,并返回指针 \(j\) 。
图 10-8 将查找边界转化为查找元素
图解 10-8:用半整数查找左右边界
在整数数组中,借助两个不存在的半整数定位重复值的左右边界。
有序整数数组为 nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15],目标元素 target = 6(占据索引 2 至 6)。由于数组中全是整数,构造出的半整数 target - 0.5 = 5.5 与 target + 0.5 = 6.5 必然不在数组中。
当使用双闭区间二分查找一个数组中不存在的目标值时,循环无需处理相等分支,最终搜索区间为空时,指针 i 必指向首个大于该目标的元素,指针 j 必指向最右一个小于该目标的元素。若不存在更大的元素,i = n;若不存在更小的元素,j = −1,此时对应指针位于数组外。
画面左侧展示“查找最左一个 target”等价于“查找 target - 0.5”(即 5.5):查找结束时 j = 1(指向 3),i = 2(指向首个大于 5.5 的元素,即最左一个 6),返回 i = 2 即得左边界。画面右侧展示“查找最右一个 target”等价于“查找 target + 0.5”(即 6.5):查找结束时 j = 6(指向最右一个小于 6.5 的元素,即最右一个 6),i = 7(指向 10),返回 j = 6 即得右边界。
该方法依赖输入数组仅含整数的前提(若原数组本身包含小数,则 ±0.5 可能与已有元素碰撞而失效);通用实现中若原数组可能不含 target,返回前仍需校验索引不越界且对应元素值等于 target。
代码在此省略,以下两点值得注意。
- 给定数组不包含小数,这意味着我们无须关心如何处理相等的情况。
- 因为该方法引入了小数,所以需要将函数中的变量
target改为浮点数类型(Python 无须改动)。