Требуется реализовать поиск в отсортированном массиве элемента, ближайшего к заданному значению.
В первой строке записано одно целое число N — размер отсортированного массива
(1 <= N <= 10^5). Далее записаны элементы массива ( N целых чисел, |Ai| <= 10^9). Затем
записано целое число Q— количество запросов, которые нужно обработать (1 <= Q <= 10^5). В остальных Q строках записаны целые числа Yj, определяющие запросы на поиск.
Запросы нужно обрабатывать следующим образом. Для каждого числа Yj нужно найти
в массиве A такой элемент, чтобы разность между ним и Yj была минимальной. В выходной
файл нужно вывести два целых числа через пробел: индекс найденного элемента и полученное минимальное расстояние.
Элементы массива нумеруются индексами от 0 до N − 1. Если ближайших элементов
несколько, разрешается выводить индекс любого из них. В данной задаче ответ для каждого запроса нужно находить независимо от всех
остальных запросов за время O(log N) в худшем случае.
Существует ли какое-то красивое решение?
Только надо чуть чуть изменить. В конце вы останетесь на каком-то элементе ближайшем к искомуму слева или справа.
Так что провертьте left и 2 соседних элемента на ближайшесть.
Простой
