34.Find First and Last Position of Element in Sorted Array
Given an array of integers nums
sorted in ascending order, find the starting and ending position of a given target
value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1]
.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路:
在一个有序数组中找到目标的首尾下标,要求时间复杂度为O(logn),很明显使用二分法来做,与普通二分法不同的是,需要当mid元素目标匹配的时候,判断该移动右指针走,找到左边界,还是移动左指针,找到右边界。所以需要两次二分搜索。
代码:
go:
func searchRange(nums []int, target int) []int {
var res = []int{-1, -1}
if nums == nil || len(nums) == 0 {
return res
}
// find left
low, high := 0, len(nums) - 1
for ; low + 1 < high; {
mid := low + (high - low)/2
if nums[mid] < target {
low = mid
} else {
high = mid
}
}
if nums[low] == target {
res[0] = low
} else if nums[high] == target {
res[0] = high
}
if res[0] == -1 {
return res
}
// find right
low, high = 0, len(nums) - 1
for ; low + 1 < high; {
mid := low + (high - low)/2
if nums[mid] <= target {
low = mid
} else {
high = mid
}
}
if nums[high] == target {
res[1] = high
} else if nums[low] == target {
res[1] = low
}
return res
}