Реализуйте алгоритм бинарного поиска.
Входные данные
В первой строке входных данных содержатся натуральные числа N и K (0<N, K≤100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит 109
Выходные данные
Требуется для каждого из K чисел вывести в отдельную строку «YES», если это число встречается в первом массиве, и «NO» в противном случае.
Примеры
входные данные
10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
выходные данные
NO
NO
YES
YES
NO
Решение на Python
def lower_bound(A, key):
left = -1
right = len(A)
while right - left > 1:
middle = (left + right) // 2
if A[middle] < key:
left = middle
else:
right = middle
return right
def upper_bound(A, key):
left = -1
right = len(A)
while right - left > 1:
middle = (left + right) // 2
if A[middle] <= key:
left = middle
else:
right = middle
return right
input()
A = list(map(int, input().split()))
for key in input().split():
key = int(key)
lower = lower_bound(A, key)
upper = upper_bound(A, key)
if lower < len(A) and A[lower] == key:
print('YES')
# print(lower, upper - 1)
else:
print('NO')
# print(-1)
Источник: https://informatics.msk.ru/mod/statements/view.php?id=39096&chapterid=4#1