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 |
Вставьте недостающие фрагменты кода
C++
