-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leetcode0034.py
53 lines (51 loc) · 1.49 KB
/
Leetcode0034.py
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1, -1]
# find the first occurance
start = 0
end = len(nums)-1
res = [-1, -1]
while(start+1<end):
middle = (start+end)/2
# print start, end, middle
if nums[middle]==target:
res[0] = middle
# we check if we can find one on the left side
# print res
end = middle
continue
if nums[middle]>target:
end = middle
continue
start = middle
if nums[start] == target:
res[0] = start
else:
if nums[end] == target:
res[0] = end
# find the second occurance
start = 0
end = len(nums)-1
while(start+1<end):
middle = (start+end)/2
if nums[middle]==target:
res[1] = middle
# we check if we can find one on the left side
start = middle
continue
if nums[middle]>target:
end = middle
continue
start = middle
if nums[end] == target:
res[1] = end
else:
if nums[start] == target:
res[1] = start
return res