题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 示例 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 <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
|
题目解析
常规解法-暴力-O(n)
- 利用数组有序的特点，从头到尾遍历一次数组
- 在遍历的开始，检查遍历到的元素是否等于target，遇到刚好等于target的时候，记录当前位置
- 接着遍历，检查遍历到大元素是否不等于target，遇到刚好不等于target的时候，记录当前位置的前一个位置即可
进阶解法-二分查找-O(log n)
- 基本思想：在一个区间范围里看处在中间位置的元素的值nums[mid]与目标元素target的大小关系，进而决定目标值落在哪一个部分里
- 目标元素target在有序数组中很可能存在多个
- 使用二分查找方法看到的处在中间元素的值nums[mid]恰好等于目标元素target的时候，还需要继续查找（继续做二分查找）
方法1：使用sort.SearchInts
1
2
3
4
5
6
7
8
9
|
func searchRange(nums []int, target int) []int {
leftmost := sort.SearchInts(nums, target)
if leftmost == len(nums) || nums[leftmost] != target {
return []int{-1, -1}
}
rightmost := sort.SearchInts(nums, target + 1) - 1
return []int{leftmost, rightmost}
}
|
方法2：自己实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func searchRange(nums []int, target int) []int {
left := search(nums, target)
if left == len(nums) || nums[left] != target {
return []int{-1,-1}
}
right := search(nums, target+1) - 1
return []int{left, right}
}
func search(nums []int, target int) int {
l, r := 0, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if nums[mid] < target {
l = mid + 1
} else {
r = mid - 1
}
}
return l
}
|
参考链接
leetcode题解_来跟高手学写二分查找
leetcode题解_二分查找+模板go
leetcode题解_Go 二分查找的变种
