题目

给定一个按照升序排列的整数数组 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]

方案一

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

    return -1
}

func searchRange(nums []int, target int) []int {
    var index = binarySearch(nums, target)
    if index == -1 {return []int{-1, -1}}
    // 往前
    var left, right = index, index
    for {
        if left - 1 >= 0 && nums[left - 1] == target {
            left = left - 1
            continue
        }
        if right + 1 < len(nums) && nums[right + 1] == target {
            right = right + 1
            continue
        }
        break
    }

    return []int{left, right}
}

• 先使用二分查找找到目标值位置
• 根据二分查找的值，往前后迭代

原文

https://leetcode-cn.com/explore/learn/card/binary-search/211/template-iii/844/