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]
public int[] searchRange(int[] nums, int target) {
int[] res = {-1, -1};
int lo = 0, hi = nums.length - 1;
while(nums[lo] < nums[hi]) {
int mid = lo + (hi - lo)/2;
if(nums[mid] > target) {
hi = mid - 1;
} else if(nums[mid] < target) {
lo = mid + 1;
} else {
if(nums[lo] == nums[mid]) {
hi--;
}else {
lo++;
}
}
}
if(nums[lo] == nums[hi] && nums[lo]== target) {
res[0] = lo;
res[1] = hi;
}
return res;
}
