Модуль: Линейный и двоичный поиск элементов в массиве


Задача

7/7

Реализация двоичного поиска

Теория Нажмите, чтобы прочитать/скрыть

Сравнение алгоритмов линейного и двоичного поиска по числу сравнений
 
Примеры
Линейный поиск Двоичный поиск
2 2 2
16 16 5
1024 1024 11
1048576 1048576 21

Плюсы двоичной сортировки в том, что выполняется она быстрее.
Минусы - необходим предварительно отсортированный массив.

 

Задача

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

Входные данные 
В первой строке входных данных содержатся натуральные числа N и K (0<N,K<=100000). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию, а в третьей строке – K элементов второго массива. Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 109.

Выходные данные 
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.
 
Примеры
Входные данные Выходные данные
1 10 5
1 2 3 4 5 6 7 8 9 10
-2 0 4 9 12
NO
NO
YES
YES
NO