Проверяет знание алгоритма бинарного поиска для нахождения ближайшего элемента в отсортированном массиве.
Когда массив отсортирован, линейный поиск (проход по всем элементам) неэффективен. Бинарный поиск позволяет найти элемент или его ближайшее значение за логарифмическое время. Суть алгоритма: на каждом шаге мы сравниваем искомое значение со средним элементом массива и отбрасываем половину, где элемент точно не может находиться.
Мы ищем позицию, куда можно вставить искомое значение, сохраняя порядок сортировки. Затем проверяем два соседних элемента — слева и справа от этой позиции — и выбираем тот, разница с которым минимальна. Если массив пуст или содержит один элемент, ответ очевиден.
function findNearest(arr, target) {
if (arr.length === 0) return null;
let left = 0, right = arr.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return arr[mid];
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
// left — позиция для вставки
if (left === 0) return arr[0];
if (left === arr.length) return arr[arr.length - 1];
// Сравниваем соседей
const prev = arr[left - 1];
const next = arr[left];
return Math.abs(prev - target) <= Math.abs(next - target) ? prev : next;
}Вывод: Бинарный поиск — стандартный и эффективный способ ускорить поиск в отсортированных данных. Его стоит применять везде, где массив отсортирован и требуется найти элемент или его ближайшее значение, так как это даёт значительный прирост производительности по сравнению с линейным перебором.
