class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if len(nums) == 0:
return [-1, -1]
if len(nums) == 1:
if nums[0] == target:
return [0, 0]
else:
return [-1, -1]
left = self.findLeftMost(nums, target)
if left == -1:
return [-1, -1]
right = self.findRightMost(nums, target)
return [left, right]
def findLeftMost(self, nums, target) -> int:
low, high = 0, len(nums)-1
while low + 1 < high:
mid = low + (high-low) // 2
if nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid - 1
else:
high = mid
if nums[low] == target:
return low
if nums[high] == target:
return high
return -1
def findRightMost(self, nums, target) -> int:
low, high = 0, len(nums)-1
while low + 1 < high:
mid = low + (high-low) // 2
if nums[mid] < target:
low = mid + 1
elif nums[mid] > target:
high = mid - 1
else:
low = mid
if nums[high] == target:
return high
if nums[low] == target:
return low
return -1
vector<int> searchRange(vector<int>& nums, int target) {
//lower bound
int start = 0, end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target){
end = mid;
} else{
start = mid;
}
}
int left;
if(nums[start] == target){
left = start;
}
else if(nums[end] == target){
left = end;
}
else{
return {-1, -1};
}
//upper bound
start = 0, end = nums.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid;
} else{
end = mid;
}
}
int right;
if (nums[end] == target) {
right = end;
}
else if (nums[start] == target) {
right = start;
}
else {
return {-1, -1};
}
return {left, right};
}