Copy Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Copy Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Copy Input: nums = [], target = 0
Output: [-1,-1]
Copy Approach 2:
Find using BS
Find the position of Left side, if left side exists then only right boundary exixts
Then find this target once for left , Take target +1 for right boundary
Then return ans
Copy class Solution {
public :
int left_index ( vector < int > & nums , int target){
int low = 0 , high = nums . size () - 1 ;
while (low <= high){
int mid = low + (high - low) / 2 ;
if ( nums [mid] == target){
if (mid == 0 )
return mid;
else if ( nums [mid] != nums [mid - 1 ])
return mid;
else
high = mid - 1 ;
}
else if ( nums [mid] > target)
high = mid - 1 ;
else
low = mid + 1 ;
}
return - 1 ;
}
int right_index ( vector < int > & nums , int target){
int low = 0 , high = nums . size () - 1 ;
while (low <= high){
int mid = low + (high - low) / 2 ;
if ( nums [mid] == target){
if (mid == nums . size () - 1 )
return mid;
else if ( nums [mid] != nums [mid + 1 ])
return mid;
else
low = mid + 1 ;
}
else if ( nums [mid] > target)
high = mid - 1 ;
else
low = mid + 1 ;
}
return - 1 ;
}
vector < int > searchRange ( vector < int > & nums , int target) {
vector <int> ans;
ans . push_back ( left_index (nums , target));
ans . push_back ( right_index (nums , target));
return ans;
}
};
Copy class Solution {
private :
int lower_bound ( vector < int > & nums , int low , int high , int target){
while (low <= high){
int mid = (low + high) >> 1 ;
if ( nums [mid] < target){
low = mid + 1 ;
}
else {
high = mid - 1 ;
}
}
return low;
}
public :
vector < int > searchRange ( vector < int > & nums , int target) {
int low = 0 , high = nums . size () - 1 ;
int startingPosition = lower_bound (nums , low , high , target);
int endingPosition = lower_bound (nums , low , high , target + 1 ) - 1 ;
if (startingPosition < nums . size () && nums [startingPosition] == target){
return {startingPosition , endingPosition};
}
return { - 1 , - 1 };
}
};