-
Notifications
You must be signed in to change notification settings - Fork 9
/
Бинарный поиск.py
41 lines (35 loc) · 926 Bytes
/
Бинарный поиск.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
def binary_search(k, a):
l, r = 0, len(a) - 1
while l <= r:
m = l + (r - l) // 2
if k == a[m]:
return m + 1
elif k > a[m]:
l = m + 1
else:
r = m - 1
return -1
def binary_search_with_counting(k, a, last:bool):
n = len(k)
l, r = 0, len(a) - 1
while l <= r:
m = l + (r - l) // 2
if k > a[m] or last and k == a[m]:
l = m + 1
elif k < a[m] or (not last) and k == a[m]:
r = m - 1
return r if last else l
def main():
result = ""
a = tuple(map(int, input().split()[1:]))
b = tuple(map(int, input().split()[1:]))
for i in b:
print(binary_search(i, a), end=' ')
def main2():
a = input()
pattern = input()
right = binary_search(pattern,a,True)
left = binary_search(pattern,a,False)
print(right - left + 1)
if __name__ == "__main__":
main()