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

题目

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

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

你必须设计并实现时间复杂度为 O(logⁿ) 的算法解决此问题。

难度：🌟🌟🌟

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 0 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹
• nums 是一个非递减数组
• -10⁹ <= target <= 10⁹

题解

本题题干说明整数数组为非递减顺序排序，因此考虑使用二分查找。因为要查找元素的第一个和最后一个位置，因此选择使用两次二分查找，分别查找排序数组中target的左边界和右边界。

注意事项：

1. mid = left + (right - left)/2 能避免整数越界
2. 当 nums[mid] == target 时，不能像常规二分查找般直接 return，因为需要查找最左和最右边界，因此处理手法上和一般二分查找略有区别
3. 要考虑 nums 为空的情况
4. 要考虑 left == right 时对应值不等于 target 的情况
5. 当计算右边界时会出现 left == right - 1 && nums[mid] = target 的情况，此时 left 不会有任何变化，程序会进入死循环，因此在计算右边界时，mid 需要 +1

代码实现

func searchRange(nums []int, target int) []int {
	return []int{getLeftBound(nums, target), getRightBound(nums, target)}
}

func getLeftBound(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]
			right = mid - 1
		} else if nums[mid] < target {
			// 搜索区间变为 [mid+1, right]
			left = mid + 1
		} else if nums[mid] == target {
			right = mid
		}
	}
	// 检查边界
	// nums[left] != target 是防止 left == right 时，对应值不等于 target
	// left > len(nums) 是检查 nums 是否为空
	if left >= len(nums) || nums[left] != target {
		return -1
	}
	return left // 跳出循环时, left == right 且对应的值为target,即 left或者right 为 target 的左边界
}

func getRightBound(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left < right {
		// 有一种特殊情况：当 left == right-1 && nums[mid] = target 时
		// 此时 left 不会有任何变化，会进入死循环，因此 mid 需要 + 1
		mid := left + (right-left)/2 + 1
		if nums[mid] > target {
			// 搜索区间变为 [left, mid-1]
			right = mid - 1
		} else if nums[mid] < target {
			// 搜索区间变为 [mid+1, right]
			left = mid + 1
		} else if nums[mid] == target {
			// 不能直接返回，因为要找出右边界，所以left需要右移，但不能left=mid+1,因为这样的话可能就不再满足循环条件
			// 我们要找到 left == right 且对应值为 target 的情况
			left = mid
		}
	}
	// 检查边界
	// nums[right] != target 是防止 left == right 时，对应值不等于 target
	// right < 0 是检查 nums 是否为空
	if right < 0 || nums[right] != target {
		return -1
	}
	return right // 跳出循环时，left==right 且对应值为target值，即 left或right为target的右边界
}