Find First and Last Position of Element in Sorted Array

1. Problem Description

Given an integer array nums sorted in ascending order and a target value target, find the starting and ending positions of the target value in the array.

2. Approach

1. Binary-search the lower and upper bounds
2. First perform a binary search, then search for the two bounds

3. Implementation

3.1. Binary-Search Lower and Upper Bounds

package main

func searchRange(nums []int, target int) []int {

	if len(nums) == 0 {
		return []int{-1, -1}
	}

	if target > nums[len(nums)-1] || target < nums[0] {
		return []int{-1, -1}
	}

	low := getLower(nums, target)
	high := getHigher(nums, target)

	if low == -1 {
		return []int{-1, -1}
	}

	return []int{low, high}

}

// >
func getHigher(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left+1)>>1
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] == target {
			left = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

// <=
func getLower(nums []int, target int) int {

	left := 0
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left)>>1
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			right = mid
		}
	}

	if nums[left] == target {
		return left
	}
	return -1

}

3.2. Binary Search First, Then the Bounds

func searchRange(nums []int, target int) []int {
    index := search(nums, target)
    if index == -1 {
        return []int{-1, -1}
    }
    first := searchFirst(nums, target)
    last := searchLast(nums, target)
    return []int{first, last}
}

func searchLast(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    res := -1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            left = mid+1//// Note this line: use mid+1 rather than mid, and keep res
            res = mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return res
}

func searchFirst(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    res := -1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            right = mid-1// Note this line: use mid-1 rather than mid, and keep res
            res = mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return res
}

func search(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right {
        mid := left+(right-left)/2
        if nums[mid] == target {
            return mid
        }else if nums[mid] < target {
            left = mid+1
        }else {
            right = mid -1
        }
    }
    return -1
}

4. References

• Code Thought Record: Binary Search 34 - Find First and Last Position of Element in Sorted Array - LeetCode
• Easy to Understand - Find First and Last Position of Element in Sorted Array - LeetCode