imashutosh51

Find first and Last position of Element in sorted array

Oct 6th, 2022 (edited)
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.10 KB | None | 0 0
  1. #you can reduce the space complexity by reducing the recursion to while loop.
  2. def first_pos(arr, i, j, target):
  3.     if i <= j:
  4.         mid = (i + j) // 2
  5.         if arr[mid] == target and (mid == 0 or arr[mid - 1] != target):
  6.             return mid
  7.         if arr[mid] >= target: #even if target is in mid and mid-1 both position,it will manage
  8.             return first_pos(arr, i, mid - 1, target)
  9.         else:
  10.             return first_pos(arr, mid + 1, j, target)
  11.     return -1
  12.  
  13. def last_pos(arr, i, j, target):
  14.     if i <= j:
  15.         mid = (i + j) // 2
  16.         if arr[mid] == target and (mid == len(arr) - 1 or arr[mid + 1] != target):
  17.             return mid
  18.         if arr[mid] <= target: #even if target is in mid and mid+1 both position,it will manage
  19.             return last_pos(arr, mid + 1, j, target)
  20.         else:
  21.             return last_pos(arr, i, mid - 1, target)
  22.     return -1
  23.  
  24. class Solution:
  25.     def searchRange(self, nums: List[int], target: int) -> List[int]:
  26.         a=first_pos(nums,0,len(nums)-1,target)
  27.         b=last_pos(nums,0,len(nums)-1,target)
  28.         return [a,b]
  29.        
Advertisement
Add Comment
Please, Sign In to add comment