18. 二分查找-重复元素，最左边的插入点

0 - 算法, 0.0 - 算法模版 本文总阅读量次

正文

当数组中存在重复元素时，标准的二分查找只能随机返回其中一个目标的索引。如果我们需要找到第一个出现的目标元素（最左侧边界），或者目标不存在时其应插入的位置，需要使用以下变体。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
fun searchLeftBound(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 2
        
        if (nums[mid] >= target) {
            // 如果中间值大于等于目标，说明左边界在左侧（包含当前 mid）
            // 我们继续向左收缩以寻找“第一个”目标
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    // 此时 left 就是最左侧的插入点
    // 如果要判断 target 是否存在：
    // if (left < nums.size && nums[left] == target) return left else return -1
    return left
}

使用说明

  1. 核心逻辑：

    • 关键在于 nums[mid] >= target 时执行 right = mid - 1。即使找到了目标，我们也并不立即返回，而是继续收缩右边界，试图在左侧找到更早出现的目标。
    • 循环结束后，left 变量的值即为大于等于 target 的第一个元素的索引。

  2. 适用场景：

    • 查找有序数组中第一个等于 target 的元素。
    • 查找第一个大于等于 target 的元素（Lower Bound）。
    • 统计重复元素的个数（通过左右边界相减）。

  3. 注意点：

    • 返回值 left 的范围是 [0, nums.size]。如果 target 比数组所有元素都大，left 将等于 nums.size。
    • 检查是否存在时，务必先判断 left < nums.size。
0 - 算法, 0.0 - 算法模版