-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path043-search-range.py
More file actions
36 lines (26 loc) · 993 Bytes
/
043-search-range.py
File metadata and controls
36 lines (26 loc) · 993 Bytes
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
from typing import List
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
starting_range = self.find(nums, target, True)
if starting_range == -1:
return [-1, -1]
ending_range = self.find(nums, target, False)
return [starting_range, ending_range]
def find(self, nums: List[int], target: int, first: bool) -> int:
left, right, target_position = 0, len(nums) - 1, -1
while left <= right:
mid = (right - left) // 2 + left
if nums[mid] == target:
target_position = mid
if first:
right = mid-1
else:
left = mid+1
elif nums[mid] < target:
left = mid+1
else:
right = mid-1
return target_position
print(Solution().searchRange([5, 6, 6, 6, 6, 7, 8, 9, 10, 15, 2], 6))