Find First and Last Position of Element in Sorted Array | Binary Search

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.

Binar search

# Code

• submit code
``````class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
result = []

result.append(self.left_bound(nums,target))
result.append(self.right_bound(nums,target))

return result

def left_bound(self,nums,target):
left = 0
right = len(nums) - 1

while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
right = mid - 1

if left >= len(nums) or nums[left] != target:
return -1

return  left

def right_bound(self,nums,target):
left = 0
right = len(nums) - 1

while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
left = mid +1

if right < 0 or nums[right] != target:
return  -1

return right

``````
• full code
``````class Solution:
def searchRange(self, nums, target):
result = []

result.append(self.left_bound(nums,target))
result.append(self.right_bound(nums,target))

return result

def left_bound(self,nums,target):
left = 0
right = len(nums) - 1

while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
right = mid - 1

if left >= len(nums) or nums[left] != target:
return -1

return  left

def right_bound(self,nums,target):
left = 0
right = len(nums) - 1

while left <= right:
mid = left + int((right - left) / 2)
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
elif nums[mid] == target:
left = mid +1

if right < 0 or nums[right] != target:
return  -1

return right

nums = [5, 7, 7, 8, 8, 10]
target = 8
S = Solution()
print(S.searchRange(nums,target))
``````

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2022/02/27/find-first-and-last-position-of-element-in-sorted-array-binary-search/``

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安