Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #you can reduce the space complexity by reducing the recursion to while loop.
- def first_pos(arr, i, j, target):
- if i <= j:
- mid = (i + j) // 2
- if arr[mid] == target and (mid == 0 or arr[mid - 1] != target):
- return mid
- if arr[mid] >= target: #even if target is in mid and mid-1 both position,it will manage
- return first_pos(arr, i, mid - 1, target)
- else:
- return first_pos(arr, mid + 1, j, target)
- return -1
- def last_pos(arr, i, j, target):
- if i <= j:
- mid = (i + j) // 2
- if arr[mid] == target and (mid == len(arr) - 1 or arr[mid + 1] != target):
- return mid
- if arr[mid] <= target: #even if target is in mid and mid+1 both position,it will manage
- return last_pos(arr, mid + 1, j, target)
- else:
- return last_pos(arr, i, mid - 1, target)
- return -1
- class Solution:
- def searchRange(self, nums: List[int], target: int) -> List[int]:
- a=first_pos(nums,0,len(nums)-1,target)
- b=last_pos(nums,0,len(nums)-1,target)
- return [a,b]
Advertisement
Add Comment
Please, Sign In to add comment