2021-09-21：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。要求：设计并实现时间复杂度为 O(log n) 的算法。
福大大 答案2021-09-21：
二分法。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
arr := []int{1, 2, 3, 3, 4, 6}
target := 3
ret := searchRange(arr, target)
fmt.Println(ret)
ret = searchRange2(arr, target)
fmt.Println(ret)
}
func searchRange(nums []int, target int) []int {
if len(nums) == 0 {
return []int{-1, -1}
}
L := lessMostRight(nums, target) + 1
if L == len(nums) || nums[L] != target {
return []int{-1, -1}
}
return []int{L, lessMostRight(nums, target+1)}
}
func lessMostRight(arr []int, num int) int {
L := 0
R := len(arr) - 1
M := 0
ans := -1
for L <= R {
M = L + (R-L)>>1
if arr[M] < num {
ans = M
L = M + 1
} else {
R = M - 1
}
}
return ans
}
func searchRange2(nums []int, target int) []int {
if len(nums) == 0 {
return []int{-1, -1}
}
lv := NearestIndex(nums, target)
rv := NearestIndex2(nums, target)
if lv == -1 {
return []int{-1, -1}
}
if rv == -1 {
return []int{-1, -1}
}
if lv > rv {
return []int{-1, -1}
}
return []int{lv, rv}
}
// 在arr上，找满足>=value的最左位置
func NearestIndex(arr []int, v int) int {
L := 0
R := len(arr) - 1
index := -1 // 记录最左的对号
for L <= R {
mid := L + (R-L)>>1
if arr[mid] >= v {
index = mid
R = mid - 1
} else {
L = mid + 1
}
}
return index
}
// 在arr上，找满足<=value的最右位置
func NearestIndex2(arr []int, v int) int {
L := 0
R := len(arr) - 1
index := -1 // 记录最右的对号
for L <= R {
mid := L + (R-L)>>1
if arr[mid] <= v {
index = mid
L = mid + 1
} else {
R = mid - 1
}
}
return index
}
执行结果如下：
左神java代码
![2023-08-10：景区里有m个项目，也就是项目数组为int[][] game，这是一个m*2的二维数组 景区的第i个项目有如下两个参数： game[i] = { Ki, Bi } Ki一定是负数，](https://www.kunjuke.com/file/css/thumb/2.jpg/280-180.jpg)
