Coding Interview PatternsFind First and Last Position of Element in Sorted Array
MediumModified Binary Search
Find First and Last Position of Element in Sorted Array
Explanation & Solution
Description
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.
Input:nums = [5, 7, 7, 8, 8, 10], target = 8
0
5
1
7
2
7
3
8
4
8
5
10
Output:[3, 4]
0
3
1
4
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9numsis a non-decreasing array-10^9 <= target <= 10^9
Approach
Modified Binary Search pattern
1. Phase 1 — Find the Left Bound
- Binary search for the leftmost index where
nums[index] >= target. - If
nums[mid] < target, movelo = mid + 1. Otherwisehi = mid. - After the loop, check if
nums[lo] === target. If not, return[-1, -1].
2. Phase 2 — Find the Right Bound
- Binary search for the rightmost index where
nums[index] <= target. - If
nums[mid] <= target, movelo = mid + 1. Otherwisehi = mid. - The right bound is
lo - 1.
3. Return the Range
- Return
[left, right].
🧠 Key Insight
- This uses two variants of binary search: one finds the first occurrence (left bound) and one finds the last occurrence (right bound).
Time
O(log n)two binary searches, each O(log n).Space
O(1).Visualization
Input:
[5, 7, 7, 8, 8, 10], target = 8
—
Press ▶ or use ← → to step through
Left (L)Right (R)ConvergedDone
9 steps