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

难度：⭐⭐⭐ 面试高频

考点

• 二分查找左边界（lower_bound）
• 二分查找右边界
• 循环不变量的严格维护

题目描述

给你一个按非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果不存在，返回 [-1, -1]。

函数签名

func searchRange(nums []int, target int) []int

示例

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

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

输入：nums = [], target = 0
输出：[-1,-1]

要求

1. 时间复杂度 O(logn)
2. 两次二分分别找左右边界

提示

• 左边界：找第一个 >= target 的位置（lower_bound）
• 右边界：找第一个 >= target+1 的位置再减一
• 或者分别写 findFirst 和 findLast 两个二分

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

func searchRange(nums []int, target int) []int {
	first := lowerBound(nums, target)
	if first == len(nums) || nums[first] != target {
		return []int{-1, -1}
	}
	last := lowerBound(nums, target+1) - 1
	return []int{first, last}
}

func lowerBound(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 {
			right = mid - 1
		}
	}
	return left
}