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

• Binary-search the lower and upper 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

}

4. References

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