5
Find First and Last Position of Element in Sorted Array - Python
source link: https://dev.to/saipavan_seelamsetty/find-first-and-last-position-of-element-in-sorted-array-python-4moi
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Find First and Last Position of Element in Sorted Array - Python
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109
def searchRange(self, numbers: List[int], target: int) -> List[int]:
result=[-1,-1]
l=0
h=len(numbers)-1
while l<=h:
mid=(l+h)//2
if target>numbers[mid]:
l=mid+1
elif target<numbers[mid]:
h=mid-1
else:
result[0]=mid
h=mid-1
l=0
h=len(numbers)-1
while l<=h:
mid=(l+h)//2
if target>numbers[mid]:
l=mid+1
elif target<numbers[mid]:
h=mid-1
else:
result[1]=mid
l=mid+1
return result
Enter fullscreen mode
Exit fullscreen mode
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK