Задачи
Тернарный поиск в массиве
Тернарный поиск в массиве
Тернарный поиск принадлежит классу алгоритмов "Разделяй и Властвуй" и может быть использован для поиска элемента в отсортированном массиве. Он аналогичен бинарному поиску. Однако в случае тернарного поиска массив делится на три равные части, после чего определяется в какой из этих частей лежит ключ (искомый элемент).
Задан отсортированный массив $n$ целых чисел. Вам следует ответить на $q$ запросов: содержится ли заданное число $x$ в массиве.
\InputFile
Первая строка содержит два числа $n$ и $q~(n, q \le 10^6)$. Вторая строка содержит $n$ целых чисел, отсортированных по возрастанию. Каждая из следующих $q$ строк содержит значение $x$. Числа в массиве не превышают по модулю $10^9$.
\OutputFile
Для каждого значения $x$ выведите в отдельной строке "\textbf{YES}" если $x$ присутствует в массиве и "\textbf{NO}" иначе.
Входные данные #1
6 3 2 4 4 8 11 14 10 4 2
Выходные данные #1
NO YES YES
Входные данные #2
8 4 -8 -8 -1 1 3 4 6 8 4 10 -4 -8
Выходные данные #2
YES NO NO YES