给定一个按照升序排列的整数数组 nums
,和一个目标值 target
。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-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]
本题采用二分法
定义高低两个指针low
,high
,另中间指针为mid=(low+high)/2
,如果结果在左半部分,那么high=mid
,如果结果在右半部分,那么low=mid+1
,当low>=high
的时候跳出循环,也有可能在中间的某个查找过程中就找到了,此时low<high
在本题中,当循环退出的时候会有两种情况:
low>high
,那么此时结果必定是没有找到结果,也就是查找的目标不在数组中low=high
,那么此时的结果有可能在数组中,直接判断此时low
在数组中指向的元素是不是查找的目标即可index
就可以了func searchRange(nums []int, target int) []int {
low, high := 0, len(nums)-1
for low < high {
mid := (low + high) / 2
if nums[mid] >= target {
high = mid
} else {
low = mid + 1
}
}
if low == high {
// 此时有可能找到了元素
if nums[low] == target {
// 此时找到了这个元素,并且这是第一个元素
index := low
for ; index < len(nums); index++ {
if nums[index] != target {
break
}
}
return []int{low, index - 1}
}
}
return []int{-1, -1}
}
leetcode之34在排序数组中查找元素的第一个和最后一个位置Golang
原文:https://www.cnblogs.com/gyyyl/p/13975706.html