Find First and Last Position of Element in Sorted Array

Given a sorted array and a target value, return the first and last position of the target. If the target is not found, return [-1, -1].

Function signature

func SearchRange(nums []int, target int) []int

Inputs / outputs

• nums: sorted array of integers (non-decreasing).
• target: value to locate.
• Return: a slice [first, last].

Example

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

Constraints

• 0 <= len(nums) <= 100_000

Core idea (near-solution)

Use two binary searches: one for the first index >= target and one for the first index > target.

Invariant: lower-bound binary search maintains a monotonic predicate for the target boundary.

Algorithm (step-by-step)

1. left = lowerBound(nums, target).
2. If left == len(nums) or nums[left] != target, return [-1, -1].
3. right = lowerBound(nums, target+1) - 1.
4. Return [left, right].

Correctness sketch

• Invariant: lower-bound binary search maintains a monotonic predicate for the target boundary.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

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

Walk:
- lower bound: mid=3 val=8 -> hi=3; mid=1 val=7 -> lo=2; mid=2 val=7 -> lo=3 => first=3
- upper bound: mid=3 val=8 -> lo=4; mid=5 val=10 -> hi=5; mid=4 val=8 -> lo=5 => last=4

Pitfalls to avoid

• Mixing inclusive vs exclusive hi bounds (causes off-by-one errors).
• Forgetting to check if the target exists before computing right.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• Implement lower bound with lo := 0, hi := len(nums) and loop while lo < hi.
• Use lo + (hi-lo)/2 to avoid overflow.