034.在排序数组中查找元素的第一个和最后一个位置 Find First and Last Position of Element in Sorted Array

Description

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值,返回 [-1, -1]

Example
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
Solution
//O(log n)复杂度
func searchRange(nums []int, target int) []int {
    result := []int{-1,-1}
    if len(nums) == 0{
        return result
    }
    left ,right := 0,len(nums)
    for left < right {
        mid := (left+right)/2
        if nums[mid] >= target {
            right = mid
        }else {
            left = mid+1
        }
    }
    if left >= len(nums) {
        return result
    }
    if nums[left] != target {
        return result
    }
    result[0] = left
    right = len(nums)
    for left < right {
        mid := (left + right)/2
        if nums[mid] > target {
            right = mid
        }else {
            left = mid+1
        }
    }
    result[1] = right-1
    return result
}


//O(n)复杂度
func searchRange1(nums []int, target int) []int {
    result := []int{-1,-1}
    for i :=0;i < len(nums) ;i ++ {
        if nums[i] == target {
            result[0] = i
            break
        }
    }
    if result[0] == -1 {
        return result
    }

    for i := len(nums)-1;i >=0 ;i -- {
        if nums[i] == target {
            result[1] = i
            break
        }
    }
    return result
}

leetCode地址