Find First and Last Position of Element in Sorted Array


#1

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

#2

Uses modified binary search.

func searchRange(nums []int, target int) []int {
    result := []int{-1, -1}
    if len(nums)==0 { return result }
    
    result = append(result, findLeft(nums, target), findRight(nums, target))
    
    return result
}

func findLeft(nums []int, target int)int{
    l, r := 0, len(nums)-1
    for l<r{
         m := l + (r-l)/2
        if nums[m]<target{
            l = m+1
        } else{
            r = m
        }
    }
    
    if nums[l]==target{
        return l
    }
    
    return -1
}

func findRight(nums []int, target int)int{
    l, r := 0, len(nums)-1
    index := -1
    for l<=r{
        m := l + (r-l)/2
        if nums[m]<=target{
            l = m+1
        } else {
            r = m-1
        }
        if nums[m]==target{
           index = m
        }
    }
  
    return index
}