DSA problem
Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(log n) runtime complexity.
A linear scan would solve this in O(n), but the constraint forces you to think in terms of two independent binary searches: one for the leftmost occurrence of target (its lower_bound) and one for the rightmost (upper_bound - 1). Equal elements form a contiguous block in a sorted array, so locating the block's two ends is equivalent to locating both boundaries between < target / == target and == target / > target.
A clean implementation reuses a single lowerBound helper. The leftmost index of target is lowerBound(target). The rightmost is lowerBound(target + 1) - 1, because lowerBound(target + 1) points one past the last value equal to target. After computing those two, verify that the left index is in range and that nums[left] == target; otherwise return [-1, -1].
Both bisections run in O(log n) time and use O(1) space. The technique generalizes to range queries on any sorted data: counting occurrences of x is upper(x) - lower(x), counting values in [a, b] is upper(b) - lower(a), and so on.
Examples
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]nums = [], target = 0[-1,-1]Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is a non-decreasing array.
- -10^9 <= target <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.