e-olimp 3966. An ardent collector of butterflies

Задача взята с сайта e-olymp.com.

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует $2000000000$ видов бабочек.

Чтобы не запутаться, Андрей Сергеевич присвоил каждому виду уникальный номер. Нумерация бабочек всегда начинается с единицы.

Теперь он хочет знать, есть ли бабочка с видом $K$ в его коллекции, или же её придётся добывать, затрачивая уйму сил и денег.

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

В первой строке входного файла содержится единственное число $N (1 ≤ N ≤ 100000)$ — количество видов бабочек в коллекции Андрея Сергеевича.

В следующей строке через пробел находятся $N$ упорядоченных по возрастанию чисел — номера видов бабочек в коллекции.

Все виды бабочек в коллекции имеют различные номера.

В третьей строке файла записано число $M (1 ≤ M ≤ 100000)$ — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел $M$ чисел — номера видов бабочек, наличие которых необходимо проверить.

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

Выходной файл должен содержать $M$ строчек. Для каждого запроса выведите $»YES»$, если бабочка с данным номером содержится в коллекции, и $»NO»$ — в противном случае.

Тесты:

Входные данные Выходные данные:
$1$ $7$
$10$ $47$ $50$ $63$ $89$ $90$ $99$
$4$
$84$ $33$ $10$ $82$
$NO$
$NO$
$YES$
$NO$
$2$ $10$
$1$ $4$ $7$ $11$ $12$ $43$ $44$ $67$ $344$ $355$
$5$
$1$ $2$ $4$ $44$ $45$
$YES$
$NO$
$YES$
$YES$
$NO$

Код на Haxe:

Ход решения:

Инициализируем переменные, считываем необходимые нам значения: размер коллекции $len$, элементы коллекции (массив $arr$) и количество проверяемых экспонатов $num$:

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

Суть алгоритма бинарного поиска: искомый элемент сравнивается с элементом в середине диапазона. При совпадении поиск считаем оконченным. Если совпадения нет, то, в зависимости от различия, поиск продолжается в «левой» или «правой» половине текущего диапазона. Если оказалось, что очередной диапазон имеет «нулевую» длину, это означает, что искомого элемента в исходном массиве нет. Примечание: алгоритм требует упорядоченности исходного массива по возрастанию или убыванию.

Ссылки:

Рабочий код для тестирования на try.haxe.org: Try Haxe !

Добавить комментарий