Приближенный двоичный поиск
Задача
Реализуйте алгоритм приближенного бинарного поиска.
Формат входных данных
В первой строке входных данных содержатся числа N и K (\(0< N,\ K <100001\)). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит \(2 \cdot 10^9\).
Формат выходных данных
Для каждого из K чисел выведите в отдельную строку число из первого массива, наиболее близкое к данному. Если таких несколько, выведите меньшее из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 3 5 7 9
2 4 8 1 6
|
1
3
7
1
5
|