Каким алгоритмом найти ближайшее «особенное» число?
Допустим есть проидексированное "громадное" множество натуральных чисел и есть массив "особенных" натуральных чисел (можно считать, что особенные это простые, или совершенны, или относительные координаты домиков Всех-Всех-Всех Друзей и Родственников Кролика относительно норы самого Кролика). Надо найти ближайшее "особенное_число" относительно произвольного Х. Какие есть варианты?
Я вижу два:
-- построить множество разниц X и всех "особенных_чисел" и взять наименьшее. Но если "особенных чисел" примерно столько же сколько чисел в "громадном множестве", то это долго, ведь полученное множество разниц не проиндексированно.
-- отсортировать "громадное множество" и методом удаления на единицу найти ближайшее "особенное" в одну строну, а после в другую сторону. Сравнить эти два расстояния. Но это будет долго, если "особенных" чисел мало.
Для правильного вопроса надо знать половину ответа
Если поисков будет много, то отсортировать массив "особенных" чисел.
Методом деления пополам найти два числа из массива, между которыми попадает X, найти, какое из них ближе к X.
Средний
Простой
