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]
Last updated
Was this helpful?