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

正文

当数组中存在重复元素时，如果我们需要寻找目标元素出现的最后一次索引位置（最右侧边界），或者目标不存在时其应插入的位置，需要使用以下变体。

算法模板

fun searchRightBound(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) {
            // 如果中间值小于等于目标，说明右边界可能在右侧
            // 我们继续向右移动以寻找“最后一个”目标
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    // 此时 right 就是最右侧的插入点（即最后一个小于等于 target 的元素位置）
    // 或者说 left 是第一个大于 target 的元素位置
    return right
}

使用说明

1. 核心逻辑：

   • 关键在于 nums[mid] <= target 时执行 left = mid + 1。即使找到了目标，我们也并不立即返回，而是继续收缩左边界，试图在右侧寻找最后一次出现的目标。
   • 循环结束后，right 指向的是最后一个等于 target 的元素索引。

2. 适用场景：

   • 查找有序数组中最后一个等于 target 的元素。
   • 查找最后一个小于等于 target 的元素（Upper Bound 变体）。
   • 统计重复元素的范围（配合左边界模板）。

3. 注意点：

   • 返回值 right 的范围是 [-1, nums.size - 1]。如果 target 比数组所有元素都小，right 将为 -1。
   • 检查是否存在时，务必先判断 right >= 0。
   • left 的最终位置是第一个大于 target 的元素位置。