Advertisement
imashutosh51

Find first and Last position of Element in sorted array

Oct 6th, 2022 (edited)
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<int> searchRange(vector<int>& nums, int target) {
  4.         vector<int> ans;
  5.         vector<int>::iterator l, r;
  6.         l=lower_bound(nums.begin(),nums.end(),target);
  7.         r=upper_bound(nums.begin(),nums.end(),target);
  8.         if(l==nums.end() || nums[l-nums.begin()]!=target || l==r){
  9.             ans.push_back(-1);ans.push_back(-1); return ans;
  10.         }
  11.         ans.push_back(l-nums.begin());
  12.         ans.push_back(r-nums.begin()-1);
  13.         return ans;
  14.     }
  15. };
  16.  
  17. #Python
  18. from typing import List
  19.  
  20. def first_element(nums, l, r, target):
  21.     if l <= r:
  22.         mid = (l + r) // 2
  23.         if nums[mid] == target:
  24.             if mid == 0 or nums[mid - 1] != target:
  25.                 return mid
  26.             return first_element(nums, l, mid - 1, target)
  27.         elif nums[mid] < target:
  28.             return first_element(nums, mid + 1, r, target)
  29.         else:
  30.             return first_element(nums, l, mid - 1, target)
  31.     return -1
  32.  
  33. def last_element(nums, l, r, target):
  34.     if l <= r:
  35.         mid = (l + r) // 2
  36.         if nums[mid] == target:
  37.             if mid == r or nums[mid + 1] != target:
  38.                 return mid
  39.             return last_element(nums, mid + 1, r, target)
  40.         elif nums[mid] < target:
  41.             return last_element(nums, mid + 1, r, target)
  42.         else:
  43.             return last_element(nums, l, mid - 1, target)
  44.     return -1
  45.  
  46. class Solution:
  47.     def searchRange(self, nums: List[int], target: int) -> List[int]:
  48.         if not nums:
  49.             return [-1, -1]
  50.         a = first_element(nums, 0, len(nums) - 1, target)
  51.         if a == -1:
  52.             return [-1, -1]
  53.         b = last_element(nums, 0, len(nums) - 1, target)
  54.         return [a, b]
  55.  
  56.  
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement