在排序数组中查找元素的第一个和最后一个位置
leetcode34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 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]
示例 3：
输入：nums = [], target = 0 输出：[-1,-1]
思路
题目要求
- 在升序数组中查找目标元素的索引区间
- 若未找到目标元素，则返回
[-1, -1]
在升序数组中查找目标元素，考虑使用二分查找法。但需要对二分法做出适当改变。
由于目标元素在数组中可能重复，所以使用二分法时需要在找到目标元素后，继续再向左和向右寻找左边界和右边界。
由于数组是升序的，所以重复元素在数组中也一定是连续的。
寻找左边界就是寻找第一个大于等于目标元素的元素的索引，寻找有边界就是寻找第一个大于目标元素的元素的索引。
注意
- 寻找左边界：当找到目标元素后，判断当前元素
nums[mid]，若是mid=0或nums[mid-1] < target，则无需继续向左寻找，左边界就是当前元素的索引mid。反之，执行right = mid - 1，继续左区间中寻找左边界。 - 寻找右边界：当找到目标元素后，判断当前元素
nums[mid]，若是mid=len(nums)-1或nums[mid+1] > target，则无需继续向左寻找，左边界就是当前元素的索引mid。反之，执行left = mid + 1，继续右区间中寻找右边界。
代码
Go
// 找左边界 func getLeftBorder(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 if nums[mid] > target { right = mid - 1 } else if nums[mid] == target && (mid == 0 || nums[mid-1] < target) { return mid } else { right = mid - 1 } } return -1 } //找右边界 func getRightBorder(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 if nums[mid] > target { right = mid - 1 } else if nums[mid] == target && (mid == len(nums)-1 || nums[mid+1] > target) { return mid } else { left = mid + 1 } } return -1 } func searchRange(nums []int, target int) []int { leftBorder := getLeftBorder(nums, target) rightBorder := getRightBorder(nums, target) return []int{leftBorder, rightBorder} }
