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
}