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 <= 109class Solution {
private int solveForStart(int[] nums, int lt, int rt, int target) {
int ans = -1;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (nums[mid] < target)
lt = mid + 1;
else if (nums[mid] >= target) {
if (nums[mid] == target)
ans = mid;
rt = mid - 1;
}
}
return ans;
}
private int solveForEnd(int[] nums, int lt, int rt, int target) {
int ans = -1;
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (nums[mid] <= target) {
if (nums[mid] == target)
ans = mid;
lt = mid + 1;
} else if (nums[mid] > target)
rt = mid - 1;
}
return ans;
}
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[2];
ans[0] = solveForStart(nums, 0, nums.length - 1, target);
ans[1] = solveForEnd(nums, 0, nums.length - 1, target);
return ans;
}
}