Двоичный поиск [Binary search] Поиск ближайшего в массиве

Давайте научимся решать следующую задачу — в отсортированном массиве нужно быстро находить ближайший к числу x элемент (x меняется от запроса к запросу). Если бы нужно было находить элемент в точности равный x, то мы могли бы использовать хеш-таблицу. Но если элемента x в массиве нет, то хеш-таблица просто укажет это. Нам же в таком случае нужно решить следующие две задачи: Найти максимальный элемент, не больше чем x (ближайший к x слева) Найти минимальный элемент, не меньше чем x (ближайший к x справа) Выбрав из этих двух вариантов тот, который ближе к числу x мы решим задачу (так как все элементы левее и правее будет только дальше от x). Рассмотрим алгоритм бинарного поиска для решения первой задачи (максимальный элемент, не больший x). ✔ Лектор: Павел Маврин ✔ Основной сайт:
✔ Дополнительные домашние задания, описание к урокам и многое другое можно найти на сайте Codeforces: