Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<int> searchRange(vector<int>& nums, int target) {
- vector<int> ans;
- vector<int>::iterator l, r;
- l=lower_bound(nums.begin(),nums.end(),target);
- r=upper_bound(nums.begin(),nums.end(),target);
- if(l==nums.end() || nums[l-nums.begin()]!=target || l==r){
- ans.push_back(-1);ans.push_back(-1); return ans;
- }
- ans.push_back(l-nums.begin());
- ans.push_back(r-nums.begin()-1);
- return ans;
- }
- };
- #Python
- from typing import List
- def first_element(nums, l, r, target):
- if l <= r:
- mid = (l + r) // 2
- if nums[mid] == target:
- if mid == 0 or nums[mid - 1] != target:
- return mid
- return first_element(nums, l, mid - 1, target)
- elif nums[mid] < target:
- return first_element(nums, mid + 1, r, target)
- else:
- return first_element(nums, l, mid - 1, target)
- return -1
- def last_element(nums, l, r, target):
- if l <= r:
- mid = (l + r) // 2
- if nums[mid] == target:
- if mid == r or nums[mid + 1] != target:
- return mid
- return last_element(nums, mid + 1, r, target)
- elif nums[mid] < target:
- return last_element(nums, mid + 1, r, target)
- else:
- return last_element(nums, l, mid - 1, target)
- return -1
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- if not nums:
- return [-1, -1]
- a = first_element(nums, 0, len(nums) - 1, target)
- if a == -1:
- return [-1, -1]
- b = last_element(nums, 0, len(nums) - 1, target)
- return [a, b]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement