Проверяет понимание алгоритмов вставки в отсортированный массив с сохранением порядка элементов.
Вставка элемента в отсортированный массив с сохранением порядка требует сначала найти позицию, где новый элемент должен находиться, чтобы массив остался отсортированным. Затем нужно вставить элемент на эту позицию, сдвинув все последующие элементы вправо.
Самый простой способ — линейный поиск: проходим по массиву и сравниваем каждый элемент с вставляемым. Как только находим элемент, который больше или равен вставляемому, это и есть нужная позиция. Для больших массивов эффективнее использовать бинарный поиск, так как он работает за O(log n) вместо O(n).
function insertSorted(arr, element) {
// Бинарный поиск позиции
let left = 0;
let right = arr.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] < element) {
left = mid + 1;
} else {
right = mid;
}
}
// Вставка на найденную позицию
arr.splice(left, 0, element);
return arr;
}
const sorted = [1, 3, 5, 7];
insertSorted(sorted, 4); // [1, 3, 4, 5, 7]Этот подход используется в алгоритмах сортировки вставками, при работе с упорядоченными коллекциями данных, в базах данных для поддержания индексов, а также в любых задачах, где требуется динамически добавлять элементы в отсортированный список.
Вставка с сохранением порядка — базовая операция, которая полезна при работе с отсортированными данными. Для небольших массивов можно использовать линейный поиск, для больших — бинарный, чтобы ускорить процесс.
