题目描述#

给定一个按非递减顺序排列的整数数组 nums，以及一个目标值 target。需要找出 target 在数组中第一次出现的位置和最后一次出现的位置。

如果数组中不存在 target，返回 [-1, -1]。题目要求时间复杂度为 O(log n)，所以不能慢慢扫一遍啦，拜托，边界问题当然要交给二分查找嘛～

重复元素挤在一起？咱把最左和最右都拍下来～

思路#

这题不是只判断 target 是否存在，而是要找它连续出现区间的左右边界。直接找到某一个 target 还不够，因为它可能在中间，左边和右边还藏着同样的值。

第一轮二分找最左侧位置，也就是第一个 >= target 的下标。只要 nums[mid] >= target，就说明答案可能在 mid，也可能在更左边，所以让 right = mid - 1；否则 nums[mid] < target，目标只能在右边，让 left = mid + 1。循环结束后，如果 left 没越界并且 nums[left] == target，它就是左边界，否则左边界记为 -1。

第二轮二分找最右侧位置，也就是最后一个 <= target 的下标。只要 nums[mid] <= target，说明答案可能在 mid，也可能在更右边，于是让 left = mid + 1；否则目标只能在左边，让 right = mid - 1。循环结束后，如果 right 没越界并且 nums[right] == target，它就是右边界，否则右边界记为 -1。

没错没错，左边界看 left，右边界看 right。照片当然不是现实，但如果把同一个数字出现的起点和终点都拍清楚，答案就不会偷偷跑掉啦。好啦，三、二、一，咔嚓！

思维边界#

• 空数组：需要先判断 len(nums) == 0，否则后续二分没有有效区间。
• 左边界：第一轮二分结束后，left 是第一个 >= target 的位置。
• 右边界：第二轮二分结束后，right 是最后一个 <= target 的位置。
• 越界检查：访问 nums[left] 前要确认 left < len(nums)，访问 nums[right] 前要确认 right >= 0。
• 不存在目标值：左右边界都需要单独校验是否真的等于 target，不能只看插入位置。

本姑娘小提示：找左边界用“第一个 >=”，找右边界用“最后一个 <=”～

代码#

func searchRange(nums []int, target int) []int {
	left, right := 0, len(nums)-1
	ans := []int{}
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	// 先找最左侧
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left < len(nums) && nums[left] == target {
		ans = append(ans, left)
	} else {
		ans = append(ans, -1)
	}

	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
		}
	}
	if right >= 0 && nums[right] == target {
		ans = append(ans, right)
	} else {
		ans = append(ans, -1)
	}
	return ans
}