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].

Why this is worth learning

An equality range is the difference between two boundaries: first value >=target and first value >target. Two logarithmic searches avoid a linear scan through a long duplicate run.

Before coding: one-minute experiment

For [2,2,2,4,5] and target 2, what are lower bound, upper bound, and the returned range?

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)

Finding one target and scanning outward is correct, but an array filled with target still costs O(n). Sortedness gives two monotone questions: where do values stop being <target, and where do they stop being <=target? Their boundaries enclose exactly the equal block. This derives two searches with different equality branches, without computing target+1.

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 = upperBound(nums, target) - 1, where upperBound finds the first value strictly greater than target by comparing directly with target.
4. Return [left, right].

Correctness sketch

The lower-bound search partitions indices into values below target and values at least target. If its result is outside the array or unequal to target, no matching entry exists. Otherwise the upper-bound search partitions values at most target from those strictly greater. Sortedness means all target occurrences form one contiguous block beginning at lower and ending immediately before upper. Returning [lower,upper-1] is therefore exact. The two predicates differ only in strictness, but that difference is what separates the beginning and end of duplicates.

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.

Debugging lens

Test all-equal arrays, no match, and an empty input. Do not compute upper bound by searching target+1; adding one can overflow at the largest int. The reference compares <=target directly.

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.

Reconstruction checkpoint

For [2,2,2,4,5] and target 2, what are lower bound, upper bound, and the returned range?

Return to Binary Search · Module quiz