当前位置：首页 > news >正文

二分查找边界

news 2025/10/31 17:55:47

二分查找边界

Q：给定一个长度为𝑛的有序数组nums ，其中可能包含重复元素。请返回数组中最左一个元素target的索引。若数组中不包含该元素，则返回−1 。

查找左边界

回忆二分查找插入点的方法，搜索完成后 𝑖 指向最左一个target ，因此查找插入点本质上是在查找最左一个target的索引。

考虑通过查找插入点的函数实现查找左边界。请注意，数组中可能不包含target ，这种情况可能导致以下两种结果。

插入点的索引𝑖越界。
元素 nums[i] 与 target 不相等。

当遇到以上两种情况时，直接返回 −1 即可。

/* 二分查找最左一个 target */
int binarySearchLeftEdge(int[] nums, int target) {// 等价于查找 target 的插入点int i = binary_search_insertion.binarySearchInsertion(nums, target);// 未找到 target ，返回 -1if (i == nums.length || nums[i] != target) {return -1;}// 找到 target ，返回索引 ireturn i;
}

查找右边界

最直接的方式是修改代码，替换在nums[m] == target情况下的指针收缩操作。

/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(int[] nums, int target) {int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]while (i <= j) {int m = i + (j - i) / 2; // 计算中点索引 mif (nums[m] < target) {i = m + 1; // target 在区间 [m+1, j] 中} else if (nums[m] > target) {j = m - 1; // target 在区间 [i, m-1] 中} else {i = m + 1; // 首个大于 target 的元素在区间 [m+1, j] 中}}// 返回插入点 jreturn j;
}

下面我们介绍两种更加取巧的方法

复用查找左边界

实际上，我们可以利用查找最左元素的函数来查找最右元素，具体方法为：将查找最右一个 target 转化为查找最左一个target + 1。 查找完成后，指针𝑖 指向最左一个target + 1（如果存在），而 𝑗 指向最右一个target ，因此返回𝑗 即可。

请注意，返回的插入点是𝑖 ，因此需要将其减 1 ，从而获得j

/* 二分查找最右一个 target */
int binarySearchRightEdge(int[] nums, int target) {// 转化为查找最左一个 target + 1int i = binary_search_insertion.binarySearchInsertion(nums, target + 1);// j 指向最右一个 target ，i 指向首个大于 target 的元素int j = i - 1;// 未找到 target ，返回 -1if (j == -1 || nums[j] != target) {return -1;}// 找到 target ，返回索引 jreturn j;
}