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

一、问题描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

进阶:

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

二、方案一：二分查找

1、思路

通过二分查找，查找等于目标值的元素位置。基于上面的位置，向左查找得到第一个位置，向右查找得到最后一个位置

2、代码实现

func searchRange(nums []int, target int) []int {
    // 初始化两个指针，分别指向数组的开始和结束
    left, right := 0, len(nums)-1
    // 初始化两个变量，分别用于存储目标值的第一个和最后一个位置
    first, last := -1, -1

    // 使用二分查找来找到目标值的位置
    for left <= right {
        // 计算中间位置
        mid := left + (right-left)/2
        // 如果中间位置的值等于目标值
        if nums[mid] == target {
            // 更新第一个位置
            first = mid
            // 向左查找第一个等于目标值的位置
            for first >= 0 && nums[first] == target {
                first--
            }
            // 更新最后一个位置
            last = mid
            // 向右查找最后一个等于目标值的位置
            for last < len(nums) && nums[last] == target {
                last++
            }
            // 返回第一个和最后一个位置
            return []int{first + 1, last - 1}
        } else if nums[mid] < target {
            // 如果中间位置的值小于目标值，移动左指针
            left = mid + 1
        } else {
            // 如果中间位置的值大于目标值，移动右指针
            right = mid - 1
        }
    }

    // 如果二分查找结束后没有找到目标值，返回[-1, -1]
    return []int{first, last}
}

3、复杂度分析

• 时间复杂度：O(log n)，其中 n 是数组的长度。
• 空间复杂度：O(1)，不需要额外的空间。