2021-09-21：给定一个按照升序排列的整数数组 nums，和

原创

福大大架构师每日一题

修改于 2021-09-22 03:13:16

3660

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
}