Introduction
LeetCode 34: Find First and Last Position of Element in Sorted Array is a staple binary search problem that teaches you how to apply binary search variations to find boundaries of a target value.
It challenges your ability to tweak binary search to find the leftmost (first) and rightmost (last) positions in a sorted array.
Problem Statement
Given an array of integers nums sorted in ascending order, and an integer target, return the starting and ending position of the target value.
If the target is not found, return [-1, -1].
Examples
go
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
go
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
go
Input: nums = [], target = 0
Output: [-1,-1]
Approach: Two Binary Searches
Use binary search twice:
- Once to find the leftmost (first) occurrence.
- Once to find the rightmost (last) occurrence.
This guarantees O(log n) time complexity.
Go Implementation
go
func searchRange(nums []int, target int) []int {
return []int{findFirst(nums, target), findLast(nums, target)}
}
func findFirst(nums []int, target int) int {
left, right := 0, len(nums)-1
result := -1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
result = mid
right = mid - 1 // continue searching left
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return result
}
func findLast(nums []int, target int) int {
left, right := 0, len(nums)-1
result := -1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
result = mid
left = mid + 1 // continue searching right
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return result
}
Example Walkthrough
go
Input: nums = [5,7,7,8,8,10], target = 8
1. findFirst → binary search locates index 3 (first 8)
2. findLast → binary search locates index 4 (last 8)
Output: [3,4]
Time and Space Complexity
MetricComplexityTime ComplexityO(log n)Space ComplexityO(1)
The algorithm performs two separate binary searches, each in O(log n) time.
Edge Cases
- Array is empty → return
[-1, -1]
- Target not present → return
[-1, -1]
- Target appears once → both indices are the same
Key Takeaways
- This is a perfect example of applying binary search not just to find an occurrence, but the exact boundaries.
- Slight adjustments to
left and right pointers give you precise control over which direction to continue the search.