跳转至

10.3   二分查找边界

10.3.1   查找左边界

Question

给定一个长度为 \(n\) 的有序数组 nums ,其中可能包含重复元素。请返回数组中最左一个元素 target 的索引。若数组中不包含该元素,则返回 \(-1\) 。

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

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

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

当遇到以上两种情况时,直接返回 \(-1\) 即可。代码如下所示:

binary_search_edge.py
def binary_search_left_edge(nums: list[int], target: int) -> int:
    """二分查找最左一个 target"""
    # 等价于查找 target 的插入点
    i = binary_search_insertion(nums, target)
    # 未找到 target ,返回 -1
    if i == len(nums) or nums[i] != target:
        return -1
    # 找到 target ,返回索引 i
    return i
binary_search_edge.cpp
/* 二分查找最左一个 target */
int binarySearchLeftEdge(vector<int> &nums, int target) {
    // 等价于查找 target 的插入点
    int i = binarySearchInsertion(nums, target);
    // 未找到 target ,返回 -1
    if (i == nums.size() || nums[i] != target) {
        return -1;
    }
    // 找到 target ,返回索引 i
    return i;
}
binary_search_edge.java
/* 二分查找最左一个 target */
int binarySearchLeftEdge(int[] nums, int target) {
    // 等价于查找 target 的插入点
    int i = binary_search_insertion.binarySearchInsertion(nums, target);
    // 未找到 target ,返回 -1
    if (i == nums.length || nums[i] != target) {
        return -1;
    }
    // 找到 target ,返回索引 i
    return i;
}
binary_search_edge.cs
/* 二分查找最左一个 target */
int BinarySearchLeftEdge(int[] nums, int target) {
    // 等价于查找 target 的插入点
    int i = binary_search_insertion.BinarySearchInsertion(nums, target);
    // 未找到 target ,返回 -1
    if (i == nums.Length || nums[i] != target) {
        return -1;
    }
    // 找到 target ,返回索引 i
    return i;
}
binary_search_edge.go
/* 二分查找最左一个 target */
func binarySearchLeftEdge(nums []int, target int) int {
    // 等价于查找 target 的插入点
    i := binarySearchInsertion(nums, target)
    // 未找到 target ,返回 -1
    if i == len(nums) || nums[i] != target {
        return -1
    }
    // 找到 target ,返回索引 i
    return i
}
binary_search_edge.swift
/* 二分查找最左一个 target */
func binarySearchLeftEdge(nums: [Int], target: Int) -> Int {
    // 等价于查找 target 的插入点
    let i = binarySearchInsertion(nums: nums, target: target)
    // 未找到 target ,返回 -1
    if i == nums.endIndex || nums[i] != target {
        return -1
    }
    // 找到 target ,返回索引 i
    return i
}
binary_search_edge.js
/* 二分查找最左一个 target */
function binarySearchLeftEdge(nums, target) {
    // 等价于查找 target 的插入点
    const i = binarySearchInsertion(nums, target);
    // 未找到 target ,返回 -1
    if (i === nums.length || nums[i] !== target) {
        return -1;
    }
    // 找到 target ,返回索引 i
    return i;
}
binary_search_edge.ts
/* 二分查找最左一个 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;
}
binary_search_edge.dart
/* 二分查找最左一个 target */
int binarySearchLeftEdge(List<int> nums, int target) {
  // 等价于查找 target 的插入点
  int i = binarySearchInsertion(nums, target);
  // 未找到 target ,返回 -1
  if (i == nums.length || nums[i] != target) {
    return -1;
  }
  // 找到 target ,返回索引 i
  return i;
}
binary_search_edge.rs
/* 二分查找最左一个 target */
fn binary_search_left_edge(nums: &[i32], target: i32) -> i32 {
    // 等价于查找 target 的插入点
    let i = binary_search_insertion(nums, target);
    // 未找到 target ,返回 -1
    if i == nums.len() as i32 || nums[i as usize] != target {
        return -1;
    }
    // 找到 target ,返回索引 i
    i
}
binary_search_edge.c
/* 二分查找最左一个 target */
int binarySearchLeftEdge(int *nums, int numSize, int target) {
    // 等价于查找 target 的插入点
    int i = binarySearchInsertion(nums, numSize, target);
    // 未找到 target ,返回 -1
    if (i == numSize || nums[i] != target) {
        return -1;
    }
    // 找到 target ,返回索引 i
    return i;
}
binary_search_edge.kt
/* 二分查找最左一个 target */
fun binarySearchLeftEdge(nums: IntArray, target: Int): Int {
    // 等价于查找 target 的插入点
    val i = binarySearchInsertion(nums, target)
    // 未找到 target ,返回 -1
    if (i == nums.size || nums[i] != target) {
        return -1
    }
    // 找到 target ,返回索引 i
    return i
}
binary_search_edge.rb
### 二分查找最左一个 target ###
def binary_search_left_edge(nums, target)
  # 等价于查找 target 的插入点
  i = binary_search_insertion(nums, target)

  # 未找到 target ,返回 -1
  return -1 if i == nums.length || nums[i] != target

  i # 找到 target ,返回索引 i
end
可视化运行

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\) :

binary_search_edge.py
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
binary_search_edge.cpp
/* 二分查找最右一个 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;
}
binary_search_edge.java
/* 二分查找最右一个 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;
}
binary_search_edge.cs
/* 二分查找最右一个 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;
}
binary_search_edge.go
/* 二分查找最右一个 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
}
binary_search_edge.swift
/* 二分查找最右一个 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
}
binary_search_edge.js
/* 二分查找最右一个 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;
}
binary_search_edge.ts
/* 二分查找最右一个 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;
}
binary_search_edge.dart
/* 二分查找最右一个 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;
}
binary_search_edge.rs
/* 二分查找最右一个 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
}
binary_search_edge.c
/* 二分查找最右一个 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;
}
binary_search_edge.kt
/* 二分查找最右一个 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
}
binary_search_edge.rb
### 二分查找最右一个 target ###
def binary_search_right_edge(nums, target)
  # 转化为查找最左一个 target + 1
  i = binary_search_insertion(nums, target + 1)

  # j 指向最右一个 target ,i 指向首个大于 target 的元素
  j = i - 1

  # 未找到 target ,返回 -1
  return -1 if j == -1 || nums[j] != target

  j # 找到 target ,返回索引 j
end
可视化运行

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 无须改动)。
欢迎在评论区留下你的见解、问题或建议