Given an array of integers sorted in non-decreasing order, find the starting and ending positions of a given target. If target is not in array, return [-1, -1]. Must run in O(log n).
Input: nums=[5,7,7,8,8,10], target=8 → Output: [3,4]Input: nums=[5,7,7,8,8,10], target=6 → Output: [-1,-1]
Run binary search twice: once to find the leftmost position (first occurrence) and once to find the rightmost position (last occurrence).
- findLeft: binary search where we continue searching left when nums[mid]==target.
- findRight: binary search where we continue searching right when nums[mid]==target.
- Combine both results.
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{findLeft(nums, target), findRight(nums, target)};
}
private int findLeft(int[] nums, int t) {
int lo = 0, hi = nums.length - 1, res = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == t) { res = mid; hi = mid - 1; }
else if (nums[mid] < t) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
private int findRight(int[] nums, int t) {
int lo = 0, hi = nums.length - 1, res = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == t) { res = mid; lo = mid + 1; }
else if (nums[mid] < t) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
}
- Time Complexity: O(log N)
- Space Complexity: O(1)