Задача взята с сайта 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 |
Код на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static boolean find(int search, int[] arr, int len) { boolean ret = false; int fst = 0; int lst = len - 1; while (fst <= lst) { int mid = (fst + lst) / 2; if (search == arr[mid]) { ret = true; break; } else if (search < arr[mid]) { lst = mid - 1; } else { fst = mid + 1; } } return ret; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int len = scan.nextInt(); int[] arr = new int[len]; int i; for (i = 0; i < len; i++) { arr[i] = scan.nextInt(); } int num = scan.nextInt(); int search; for (i = 0; i < num; i++) { search = scan.nextInt(); System.out.print((find(search, arr, len))? "YES\n" : "NO\n"); } } } |
Алгоритм:
Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:
|
25 26 27 28 29 30 31 32 |
Scanner scan = new Scanner(System.in); int len = scan.nextInt(); int[] arr = new int[len]; int i; for (i = 0; i < len; i++) { arr[i] = scan.nextInt(); } int num = scan.nextInt(); |
Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:
|
33 34 35 36 37 |
int search; for (i = 0; i < num; i++) { search = scan.nextInt(); System.out.print((find(search, arr, len))? "YES\n" : "NO\n"); } |
Суть алгоритма бинарного поиска: искомый элемент сравнивается с элементом в середине диапазона. При совпадении поиск считаем оконченным. Если совпадения нет, то, в зависимости от различия, поиск продолжается в «левой» или «правой» половине текущего диапазона. Если оказалось, что очередной диапазон имеет «нулевую» длину, это означает, что искомого элемента в исходном массиве нет. Примечание: алгоритм требует упорядоченности исходного массива по возрастанию или убыванию.
|
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public static boolean find(int search, int[] arr, int len) { boolean ret = false; int fst = 0; int lst = len - 1; while (fst <= lst) { int mid = (fst + lst) / 2; if (search == arr[mid]) { ret = true; break; } else if (search < arr[mid]) { lst = mid - 1; } else { fst = mid + 1; } } return ret; } |
Ссылки:
Рабочий код для тестирования на Ideone.com: Ideone.com