左边界查找

📌 问题描述

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

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

Go 代码

左闭右开区间写法

func searchLeftBound(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 < len(nums) && nums[left] == target {
        return left
    }
    return -1
}

左闭右闭区间写法

func searchLeftBoundClosed(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 {
            right = mid - 1
        }
    }
 
    if left < len(nums) && nums[left] == target {
        return left
    }
    return -1
}

🎯 算法演示

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

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

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

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

步骤4: left=1, right=0, 退出

结果: left=1（第一个2的位置）

💡 核心思想

当 nums[mid] == target 时：

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

🔗 LeetCode练习

LeetCode 34 - 在排序数组中查找元素的第一个和最后一个位置

func searchRange(nums []int, target int) []int {
    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
    }
 
    if len(nums) == 0 {
        return []int{-1, -1}
    }
 
    leftIdx := searchLeft()
    if leftIdx >= len(nums) || nums[leftIdx] != target {
        return []int{-1, -1}
    }
    return []int{leftIdx, searchRight()}
}

📚 相关主题

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

---

返回：搜索算法