右边界查找

📌 问题描述

在有序数组中查找最后一个等于目标值的位置。

例如：[1, 2, 2, 2, 3] 中查找 2，应该返回索引 3（最后一个2的位置）

Go 代码

左闭右开区间写法

func searchRightBound(nums []int, target int) int {
    left, right := 0, len(nums)
 
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid
        }
    }
 
    if left-1 >= 0 && nums[left-1] == target {
        return left - 1
    }
    return -1
}

左闭右闭区间写法

func searchRightBoundClosed(nums []int, target int) int {
    left, right := 0, len(nums)-1
 
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
 
    if right >= 0 && nums[right] == target {
        return right
    }
    return -1
}

🎯 算法演示

查找数组 [1, 2, 2, 2, 3, 4] 中 2 的右边界：

步骤1: [1, 2, 2, 2, 3, 4]
        L           M           R
        nums[2]=2 <= 2, 向右收缩

步骤2:       [2, 2, 3, 4]
              L     M     R
        nums[3]=2 <= 2, 向右收缩

步骤3:             [3, 4]
                    L=M  R
        nums[4]=3 > 2, 向左收缩

步骤4: left=4, right=3, 退出

结果: left-1=3（最后一个2的位置）

💡 核心思想

当 nums[mid] == target 时：

• 不立即返回
• 继续向右收缩：left = mid + 1
• 最终 left - 1 或 right 指向最后一个等于 target 的位置

🎯 对比：左右边界的区别

// 左边界：遇到 target 向左找
if nums[mid] >= target {
    right = mid
}
 
// 右边界：遇到 target 向右找
if nums[mid] <= target {
    left = mid + 1
}

🔗 LeetCode练习

LeetCode 34 - 完整解法

func searchRange(nums []int, target int) []int {
    if len(nums) == 0 {
        return []int{-1, -1}
    }
 
    searchLeft := func() int {
        left, right := 0, len(nums)
        for left < right {
            mid := left + (right-left)/2
            if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }
 
    searchRight := func() int {
        left, right := 0, len(nums)
        for left < right {
            mid := left + (right-left)/2
            if nums[mid] <= target {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left - 1
    }
 
    leftIdx := searchLeft()
    if leftIdx >= len(nums) || nums[leftIdx] != target {
        return []int{-1, -1}
    }
    return []int{leftIdx, searchRight()}
}

📊 边界查找总结表

目标	条件分支	返回值
第一个 >= target	nums[mid] >= target 时向左	left
最后一个 <= target	nums[mid] <= target 时向右	left - 1 或 right
第一个 > target	nums[mid] > target 时向左	left
最后一个 < target	nums[mid] < target 时向右	left - 1 或 right

📚 相关主题

• 标准二分查找 - 基础二分查找
• 左边界查找 - 查找第一个等于target的位置

---

返回：搜索算法