-
Notifications
You must be signed in to change notification settings - Fork 0
/
find_first_and_last_position_of_element_in_sorted_array.py
72 lines (60 loc) · 1.68 KB
/
find_first_and_last_position_of_element_in_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
69
70
71
72
from sys import stdin
def inp():
return stdin.readline().rstrip()
def iinp():
return int(inp())
def mp():
return map(int, inp().split())
def liinp():
return list(mp())
def solve(nums, target):
"""
if len(nums)==1:
if nums[0]==target:
return [0, 0]
else:
return [-1, -1]
elif len(nums)==0:
return [-1, -1]
start = 0
end = len(nums)-1
while nums[start]!=nums[end] and start<=end:
if nums[start]!=target and nums[end]!=target:
start += 1
end -= 1
if nums[start]==target and nums[end]!=target:
end -= 1
if nums[start]!=target and nums[end]==target:
start += 1
return [start, end] if nums[start]==target and nums[end]==target else [-1, -1]
"""
start, end = 0, len(nums)-1
first_pos = -1
last_pos = -1
# Search the first position of target in the left side
while start<=end:
mid = (start+end)//2
if nums[mid]==target:
first_pos = mid
end = mid-1
elif target<nums[mid]:
end = mid-1
elif target>nums[mid]:
start = mid+1
# Search the last position of target in the right side;
# initialize variables
start, end = 0, len(nums)-1
while start<=end:
mid = (start+end)//2
if nums[mid]==target:
last_pos = mid
start = mid+1
elif target<nums[mid]:
end = mid-1
elif target>nums[mid]:
start = mid+1
return [first_pos, last_pos]
if __name__ == "__main__":
nums = liinp()
target = iinp()
print(solve(nums, target))