Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If the target is not found in the array, return [-1, -1].
Follow up: Could you 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] <= 109 nums is a non-decreasing array. -109 <= target <= 109
public class Solution {
public int[] SearchRange(int[] nums, int target) {
var res = new int[2]{-1,-1};
int l = BinarySearchLeft(nums,target,0,nums.Length-1);
if(l==-1){
return res;
}
int r = BinarySearchRight(nums,target,0,nums.Length-1);
res[0]=l;
res[1]=r;
return res;
}
private int BinarySearchRight(int[] nums, int target, int lo, int hi){
if(lo > hi){
return -1;
}
int mid = lo + (hi-lo)/2;
if(nums.Length==0){
return -1;
}
if(mid==nums.Length-1){
if(nums[mid]==target){
return mid;
}
else{
return -1;
}
}
else if(nums[mid] == target && nums[mid+1]!=target){
return mid;
}
else if(nums[mid]<=target){
lo = mid+1;
}
else if(nums[mid]>target){
hi = mid-1;
}
return BinarySearchRight(nums,target,lo,hi);
}
private int BinarySearchLeft(int[] nums, int target, int lo, int hi){
if(lo>hi){
return -1;
}
int mid = lo + (hi - lo)/2;
if(mid == 0){
if(nums.Length==0){
return -1;
}
else if(nums[0]==target){
return 0;
}
if((nums.Length==2 && nums[1]==target)){
return 1;
}
else{
return -1;
}
}
else if(nums[mid]==target && nums[mid-1]!=target){
return mid;
}
else if(nums[mid]>=target){
hi = mid-1;
}
else if(nums[mid]<target){
lo = mid+1;
}
return BinarySearchLeft(nums, target, lo, hi);
}
}Time Complexity: O(logn)
Space Complexity: O(1)
