k элементов, наиболее близких к указанному индексу

Условие

Дан массив целых чисел, отсортированный по неубыванию (возможны дубли). Также известен индекс некоторого элемента idx и число k. Необходимо реализовать метод, который вернёт k элементов массива, значение которых отличается от значения элемента с индексом idx наименьшей абсолютной разницей.

Примеры:

arr = [1, 2, 2, 3, 4, 4, 5, 6], idx = 4, k = 2 → result = [4, 4]

arr = [1, 2, 3, 4, 5, 6], idx = 3, k = 2 → result = [4, 3] или [4, 5]

arr = [1, 2, 3, 4, 5, 6], idx = 0, k = 3 → result = [1, 2, 3]

arr = [1, 2, 2, 3, 3, 56, 78, 79, 79, 100], idx = 4, k = 3 → result = [3, 2, 3]

Ответ

Начните с элемента idx и расширяйте два указателя влево и вправо, каждый раз выбирая ближайшее по значению число. Сам элемент idx включается, как в примерах.

static int[] closest(int[] arr, int idx, int k) {
    if (idx < 0 || idx >= arr.length || k < 0 || k > arr.length)
        throw new IllegalArgumentException();
    int[] result = new int[k];
    int left = idx - 1, right = idx + 1;
    if (k == 0) return result;
    result[0] = arr[idx];
    for (int i = 1; i < k; i++) {
        if (right == arr.length || (left >= 0
                && (long) arr[idx] - arr[left] <= (long) arr[right] - arr[idx]))
            result[i] = arr[left--];
        else result[i] = arr[right++];
    }
    return result;
}

При равных расстояниях выбран левый кандидат. Long защищает разности от переполнения. Время O(k), память O(k) под результат, отсортированность выхода не требуется.