Задача №4. Двоичный поиск

Реализуйте алгоритм бинарного поиска.

Входные данные

В первой строке входных данных содержатся натуральные числа 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