<div>
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:
<pre>Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] </pre>
Example 2:
<pre>Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] </pre>
Example 3:
<pre>Input: nums = [], target = 0 Output: [-1,-1] </pre>
Constraints:
0 <= nums.length <= 10<sup>5</sup>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup>numsis a non-decreasing array.-10<sup>9</sup> <= target <= 10<sup>9</sup>
</div>
题目大意：
求有序数列中元素等于target的第一个和最后一个下标
解题思路：
用模板
解题步骤：
N/A
注意事项：
- 数组为空的情况要返回-1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40def searchRange(self, nums: List[int], target: int) -> List[int]:
first = self.first_position(nums, target)
last = self.last_position(nums, target)
return [first, last]
def last_position(self, nums, target):
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start + (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else:
start = mid
if nums[end] == target:
return end
if nums[start] == target:
return start
return -1
def first_position(self, nums, target):
if not nums:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = start+ (end - start) // 2
if target < nums[mid]:
end = mid
elif target > nums[mid]:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
算法分析：
时间复杂度为O(logn)，空间复杂度O(1)
