Информатикс

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

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

В первой строке входных данных содержатся натуральные числа $N$ и $K$ ( $0 < N, K \leq 100 000$ ). Во второй строке задаются $N$ элементов первого массива, отсортированного по возрастанию, а в третьей строке – $K$ элементов второго массива. Элементы обоих массивов — целые числа, каждое из которых по модулю не превосходит 10⁹

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

Требуется для каждого из K чисел вывести в отдельную строку «YES», если это число встречается в первом массиве, и «NO» в противном случае.

Примеры

входные данные

10 5

1 2 3 4 5 6 7 8 9 10

-2 0 4 9 12

выходные данные

NO

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)

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

Источник: https://informatics.msk.ru/mod/statements/view.php?id=39096&chapterid=4#1