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.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums is a non-decreasing array.-109 <= target <= 109The key observation for this problem is that the array is sorted, which makes binary search the most efficient strategy. Instead of scanning the array linearly, we can perform two separate binary searches: one to find the first occurrence of the target and another to find the last occurrence.
In the first search, when the target is found, we continue exploring the left half to check if an earlier occurrence exists. In the second search, after finding the target, we move toward the right half to locate the last occurrence. This technique is often called lower bound and upper bound searching.
By leveraging binary search twice, we avoid unnecessary scanning and keep the solution efficient. Each search takes logarithmic time, making the overall approach highly scalable for large arrays.
Time Complexity: O(log n) using two binary searches.
Space Complexity: O(1) since only a few variables are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Binary Searches (First and Last Occurrence) | O(log n) | O(1) |
| Linear Scan (Brute Force) | O(n) | O(1) |
take U forward
The goal is to use the binary search algorithm to achieve O(log n) time complexity. We perform two separate binary searches:
Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int findFirst(const vector<int>& nums, int target) {
7 int left = 0, right = nums.size() - 1, result = -1;
8 while (left <= right) {
9 int mid = left + (right - left) / 2;
10 if (nums[mid] >= target) {
11 if (nums[mid] == target) result = mid;
12 right = mid - 1;
13 } else {
14 left = mid + 1;
}
}
return result;
}
int findLast(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1, result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
if (nums[mid] == target) result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result = {-1, -1};
if (nums.empty()) return result;
result[0] = findFirst(nums, target);
result[1] = findLast(nums, target);
return result;
}
};In this C++ solution, we split the problem into two binary searches: one to find the first occurrence and one to find the last occurrence of the target. We ensure both searches are conditional to a sorted array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
One binary search finds the first occurrence by continuing the search on the left side after locating the target. The second binary search finds the last occurrence by exploring the right side, ensuring both boundaries are identified accurately.
Yes, variations of this problem are frequently asked in FAANG and other top tech interviews. It tests understanding of binary search patterns, boundary conditions, and efficient searching in sorted arrays.
An array combined with binary search is the best choice because the elements are already sorted. This allows us to quickly narrow the search range and find the target positions in logarithmic time.
The optimal approach uses binary search to find the first and last occurrences of the target element. By performing two modified binary searches, you can locate both boundaries efficiently in O(log n) time.