smj007

Find First & Last Position of Element in Sorted Array

Apr 19th, 2025
484
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.21 KB | None | 0 0
  1. class Solution:
  2.     def searchRange(self, nums: List[int], target: int) -> List[int]:
  3.        
  4.         def upper_bound(nums: List[int], target:int):
  5.             """Returns the index of last element"""
  6.             low, high = 0, len(nums)-1
  7.             result = -1
  8.  
  9.             while (low <= high):
  10.                 mid = (low + high)//2
  11.                 if nums[mid] <= target:
  12.                     result = mid
  13.                     low = mid + 1
  14.                 else:
  15.                     high = mid - 1
  16.  
  17.             if result != -1 and nums[result] != target:
  18.                 return -1
  19.  
  20.             return result
  21.                
  22.         def lower_bound(nums: List[int], target:int):
  23.             low, high = 0, len(nums)-1
  24.             result = -1
  25.  
  26.             while (low <= high):
  27.                 mid = (low + high)//2
  28.                 if nums[mid] >= target:
  29.                     result = mid
  30.                     high = mid - 1
  31.                 else:
  32.                     low = mid + 1
  33.  
  34.             if result != -1 and nums[result] != target:
  35.                 return -1
  36.  
  37.             return result
  38.  
  39.         start = lower_bound(nums, target)
  40.         end = upper_bound(nums, target)
  41.  
  42.         return [start, end]
  43.  
Advertisement
Add Comment
Please, Sign In to add comment