-
Notifications
You must be signed in to change notification settings - Fork 0
/
first_last_position_sorted_array.py
68 lines (54 loc) · 2.06 KB
/
first_last_position_sorted_array.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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution(object):
def searchRange(self, nums, target):
"""
Must run it in O(log n) time.
"""
if not nums:
return [-1,-1]
def b_search(nums, target, left):
lo, high = 0, len(nums)
while (lo < high):
mid = (lo + high) / 2
if nums[mid] == target:
if left:
high = mid
else:
lo = mid + 1
elif nums[mid] < target:
lo = mid + 1
else:
high = mid
return lo
left = b_search(nums, target, True)
right = b_search(nums, target, False)
if 0<= left < len(nums) and nums[left] == target:
return [left, right-1]
else:
return [-1,-1]
# lo, high = 0 , len(nums)-1
# self.answer = []
# def recur(nums, target, lo, high):
# while high >= lo:
# # import pdb; pdb.set_trace()
# mid = lo + (high-lo) // 2
# if nums[mid] == target:
# start_position = recur(nums, target, lo, mid-1)
# if start_position == -1:
# self.answer.append(mid)
# else:
# self.answer.append(start_position)
# end_position = recur(nums, target, mid+1, high)
# if end_position == -1:
# self.answer.append(mid)
# else:
# self.answer.append(end_position)
# break
# elif nums[mid] < target:
# lo = mid+1
# elif nums[mid] > target:
# high = mid-1
# return -1
# recur(nums, target, lo, high)
# print list(set(self.answer))
abc = Solution()
print (abc.searchRange([5,7,7,8,8,10], 8))