二分查找
题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例3：
输入：nums = [], target = 0
输出：[-1,-1]
题解
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
| class Solution:
def searchRange(self, nums, target):
if len(nums)==0:
return [-1,-1]
first=self.findleftpos(nums,target)
if first==-1:
return [-1,-1]
last =self.findrightpos(nums,target)
return [first,last]
def findleftpos(self,nums,target):
l=0
r=len(nums)-1
while l<r:
mid= (l+r)//2
if nums[mid]==target:
r=mid
elif nums[mid]>target:
r=mid-1
else:
l=mid+1
if nums[l]==target:
return l
else:
return -1
def findrightpos(self,nums,target):
l=0
r= len(nums)-1
while l<r:
mid = (l+r+1)//2
if nums[mid]>target:
r=mid-1
elif nums[mid]==target:
l=mid
else:
l=mid+1
return l
|
1
2
3
4
5
| a= Solution()
nums = [5,7,7,8,8,10]
target = 8
result=a.searchRange(nums,target)
print(result)
|
[3, 4]
