題目
題目大意
解題思路
Big O
- 時間複雜 :
O(log(n))
- 空間複雜 :
O(1)
來源
解答
https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/main.go
package findfirstandlastpositionofelementinsortedarray
// 時間複雜 O(log(n)), 空間複雜 O(1)
func searchRange(nums []int, target int) []int {
result := []int{}
// first index
left, right := 0, len(nums)-1
for left < right {
mid := int(uint(left+right) >> 1) // [0,1] => 0
if nums[mid] < target {
left = mid + 1
} else if nums[mid] > target {
right = mid - 1
} else {
right = mid
}
}
if left == right && nums[left] == target {
result = append(result, left)
} else {
result = append(result, -1)
}
// last index
left, right = 0, len(nums)-1
for left < right {
mid := int(uint(left+right+1) >> 1) // [0,1] => 1
if nums[mid] < target {
left = mid + 1
} else if nums[mid] > target {
right = mid - 1
} else {
left = mid
}
}
if left == right && nums[left] == target {
result = append(result, left)
} else {
result = append(result, -1)
}
return result
}
Benchmark