# 34.find-first-and-last-position-of-element-in-sorted-array

## Statement

Metadata

• 你可以设计并实现时间复杂度为 `O(log n)` 的算法解决此问题吗？

``````输入：nums = [5,7,7,8,8,10], target = 8

``````输入：nums = [5,7,7,8,8,10], target = 6

``````输入：nums = [], target = 0

• `0 <= nums.length <= 105`
• `-109 <= nums[i] <= 109`
• `nums` 是一个非递减数组
• `-109 <= target <= 109`

Metadata

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.

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`

## Solution

``````from bisect import bisect, bisect_left, bisect_right
from typing import List

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
l = bisect_left(nums, target)
r = bisect_right(nums, target)
if l == len(nums) or nums[l] != target:
return [-1, -1]
return [l, r - 1]

if __name__ == "__main__":
s = Solution()
ans = s.searchRange([5, 7, 7, 8, 8, 10], 8)
print(ans)

ans = s.searchRange([1, 2, 3, 4, 5], 10)
print(ans)
``````