Find First and Last Position of Element in Sorted Array - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Find First and Last Position of Element in Sorted Array" Problem in Go

Difficulty: Medium | Tags: Array, Binary Search

Introduction

The problem requires finding the first and last occurrence of a target value in a sorted array. Given the constraints, a binary search approach is optimal for achieving O(log n) runtime complexity.

Problem Analysis

Given a sorted array, we need to locate the starting and ending indices of a target value. If the target is not found, we return [-1, -1]. The challenge is to efficiently find these positions without scanning the entire array.

Solution Approach

We use binary search twice: first to find the leftmost occurrence of the target, and then to find the rightmost occurrence. By adjusting the binary search logic slightly, we can efficiently locate these boundaries.

Go Implementation


func searchRange(nums []int, target int) []int {
    left := findBound(nums, target, true)
    if left == -1 {
        return []int{-1, -1}
    }
    right := findBound(nums, target, false)
    return []int{left, right}
}
func findBound(nums []int, target int, isLeft bool) int {
    low, high := 0, len(nums)-1
    index := -1
    for low <= high {
        mid := low + (high-low)/2
        if nums[mid] == target {
            index = mid
            if isLeft {
                high = mid - 1
            } else {
                low = mid + 1
            }
        } else if nums[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return index
}

Complexity Analysis

The algorithm performs two binary searches, each with O(log n) time complexity. Thus, the overall time complexity is O(log n). The space complexity is O(1) as no additional space is used.

Testing and Examples

Test cases include:
1. Input: [5,7,7,8,8,10], target = 8 → Output: [3,4]
2. Input: [5,7,7,8,8,10], target = 6 → Output: [-1,-1]
3. Input: [], target = 0 → Output: [-1,-1]
Edge cases: single-element arrays and targets at the boundaries.

Best Practices and Tips

Always verify edge cases, such as empty arrays or targets not present. Using helper functions for left and right bounds keeps the code clean and modular. Ensure binary search conditions are correctly adjusted to avoid infinite loops.

Read more