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]
This algorithm finds the starting and ending positions of a target value in a sorted array by performing two specialized binary searches:
- Finding the First Occurrence:
- A binary search is used to locate the target.
- When an instance of the target is found at an index
mid, it’s a potential first occurrence. We record this index and then continue searching only in the left half (i.e., elements beforemid). This ensures we find the leftmost (first) instance. If no target is found, this search returns -1.
- Finding the Last Occurrence:
- A separate binary search is performed.
- When an instance of the target is found at
mid, it’s a potential last occurrence. We record this index and then continue searching only in the right half (i.e., elements aftermid). This ensures we find the rightmost (last) instance. If no target is found, this search returns -1.
- Result:
- The results from these two searches give the start and end indices of the target’s range. If the target isn’t found by either (or specifically, if the first search fails, the target isn’t present), the range is
[-1, -1].
- The results from these two searches give the start and end indices of the target’s range. If the target isn’t found by either (or specifically, if the first search fails, the target isn’t present), the range is
This approach is efficient because each binary search takes logarithmic time (O(log n)), making the overall algorithm run in O(log n) time.
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int firstOccurrence = findFirst(nums, target);
int lastOccurrence = findLast(nums, target);
return new int[]{firstOccurrence, lastOccurrence};
}
// Helper function to find the first occurrence of the target
private int findFirst(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int first = -1;
while (low <= high) {
int mid = low + (high - low) / 2; // Prevents potential overflow
if (nums[mid] == target) {
first = mid; // Found a target, this could be the first one
high = mid - 1; // Try to find an earlier one in the left subarray
} else if (nums[mid] < target) {
low = mid + 1; // Target is in the right subarray
} else { // nums[mid] > target
high = mid - 1; // Target is in the left subarray
}
}
return first;
}
// Helper function to find the last occurrence of the target
private int findLast(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
int last = -1;
while (low <= high) {
int mid = low + (high - low) / 2; // Prevents potential overflow
if (nums[mid] == target) {
last = mid; // Found a target, this could be the last one
low = mid + 1; // Try to find a later one in the right subarray
} else if (nums[mid] < target) {
low = mid + 1; // Target is in the right subarray
} else { // nums[mid] > target
high = mid - 1; // Target is in the left subarray
}
}
return last;
}
}
With Chinmay Murugkar 