Почему для поиска минимального расстояния можно использовать модуль разности индексов?

Почему модуль разности индексов работает для поиска минимального расстояния?

В отсортированном массиве элементы расположены в порядке возрастания (или убывания). Это означает, что разность между значениями двух элементов прямо пропорциональна разности их индексов, если массив состоит из последовательных целых чисел или имеет равномерный шаг. Однако в общем случае, когда массив отсортирован, но значения могут быть произвольными, минимальная разность между любыми двумя элементами всегда будет достигаться среди соседних элементов. Поэтому для поиска минимального расстояния достаточно вычислить разность между соседними элементами, что эквивалентно разности их индексов, если массив содержит последовательные числа.

Пример

Рассмотрим отсортированный массив: [1, 3, 6, 10]. Разность между соседними элементами: 2, 3, 4. Минимальная разность — 2 (между 1 и 3). Если бы массив был неотсортирован, пришлось бы сравнивать все пары, что заняло бы O(n^2). Благодаря сортировке, мы можем найти минимальную разность за O(n), просто пройдясь по массиву и вычислив разность между соседними элементами.

function minDifference(arr) {
  arr.sort((a, b) => a - b);
  let minDiff = Infinity;
  for (let i = 1; i < arr.length; i++) {
    minDiff = Math.min(minDiff, arr[i] - arr[i-1]);
  }
  return minDiff;
}
console.log(minDifference([10, 3, 6, 1])); // 2

Вывод

Использование модуля разности индексов для поиска минимального расстояния применимо только в контексте отсортированных массивов с последовательными значениями. В общем случае, для произвольных отсортированных данных, минимальная разность находится среди соседних элементов, что упрощает алгоритм до линейной сложности.