24. Find First and Last Position of Element in Sorted Array
mediumAsked at BookingLocate the exact date range of a target value in a sorted list — Booking applies binary search to find the first and last available nights when a property's rate matches a target price tier.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Given an array of integers nums sorted in non-decreasing order and a target, find the starting and ending position of the target value in the array. Return [-1, -1] if the target is not found. Your solution must run in O(log n) time.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9nums is a non-decreasing array-10^9 <= target <= 10^9
Examples
Example 1
nums = [5,7,7,8,8,10], target = 8[3,4]Example 2
nums = [5,7,7,8,8,10], target = 6[-1,-1]Example 3
nums = [], target = 0[-1,-1]Approaches
1. Linear scan
Scan from both ends to find first and last occurrence.
- Time
- O(n)
- Space
- O(1)
function searchRange(nums, target) {
let first = -1, last = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
if (first === -1) first = i;
last = i;
}
}
return [first, last];
}Tradeoff:
2. Two binary searches (left and right bound)
Run binary search twice — once biased left (first occurrence) and once biased right (last occurrence). O(log n).
- Time
- O(log n)
- Space
- O(1)
function searchRange(nums, target) {
function bound(isLeft) {
let lo = 0, hi = nums.length - 1, idx = -1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) {
idx = mid;
if (isLeft) hi = mid - 1;
else lo = mid + 1;
} else if (nums[mid] < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return idx;
}
return [bound(true), bound(false)];
}Tradeoff:
Booking-specific tips
Booking wants O(log n) from the start — mention the constraint before coding. The key insight to communicate: the two searches are identical except for which side you continue on when you hit the target.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.