在排序数组中查找元素的第一个和最后一个位置
leetcode34. 在排序数组中查找元素的第一个和最后一个位置
题目描述
给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
示例 1:
1
2
|
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
|
示例 2:
1
2
|
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
|
示例 3:
1
2
|
输入: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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
// 找左边界
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}
}
|
Link
GitHub