Как найти позицию вставки элемента в отсортированный массив?

Что такое позиция вставки?

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

Как работает бинарный поиск?

Бинарный поиск — это алгоритм, который работает с отсортированными данными. Он сравнивает искомое значение со средним элементом массива. Если значение меньше среднего, поиск продолжается в левой половине; если больше — в правой. Процесс повторяется, пока диапазон не сузится до одного элемента или не станет пустым.

Пример на JavaScript

function searchInsert(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid; // элемент найден
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left; // позиция вставки
}

В этом коде переменная left после завершения цикла указывает на индекс, куда нужно вставить target, чтобы массив остался отсортированным.

Где применяется?

• Вставка элементов в отсортированные списки (например, в базах данных при добавлении записи в индекс).
• Реализация бинарного поиска в стандартных библиотеках (например, bisect в Python).
• Решение задач на LeetCode и собеседованиях.

Вывод: Используйте бинарный поиск для нахождения позиции вставки, когда массив отсортирован — это даёт O(log n) время работы, что значительно быстрее линейного поиска O(n) на больших данных.