> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/34.-find-first-and-last-position-of-element-in-sorted-array.md).
# 34. Find First and Last Position of Element in Sorted Array
二分
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 <= 10``5`
* `-10``9`` ``<= nums[i] <= 10``9`
* `nums` is a non-decreasing array.
* `-10``9`` ``<= target <= 10``9`
分析
二分找边界
bisect target不存在时 left=right
```
from bisect import bisect_left, bisect_right
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = bisect.bisect_left(nums, target)
right = bisect.bisect_right(nums, target)
if left == right:
return [-1, -1]
else:
return [left, right-1]
```
九章模板必须分别判断s,e，分别计算左右边界，二分做2次。
```
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
s,e = 0,len(nums)-1
while s + 1 < e:
mid = (s + e) // 2
if nums[mid] >= target:
e = mid
else:
s = mid
if nums[s] == target:
start = s
elif nums[e] == target:
start = e
else:
return [-1,-1]
s, e = 0, len(nums) - 1
while s + 1 < e:
mid = (s + e) // 2
if nums[mid] <= target:
s = mid
else:
e = mid
if nums[e] == target:
end = e
else:
end = s
return [start,end]
```