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 <stdio.h>
2
3int binarySearchFirst(int* nums, int numsSize, int target) {
4 int left = 0, right = numsSize
This solution uses two modified binary searches, one to find the first occurrence of the target and another to find the last occurrence. The code makes sure to continue searching even if the target is found to ensure the first or last position is located.
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.