Что такое lower bound и upper bound в бинарном поиске?

Что такое lower bound и upper bound?

Lower bound и upper bound — это вариации бинарного поиска, которые позволяют находить границы вхождения элемента в отсортированном массиве. Lower bound возвращает индекс первого элемента, который не меньше заданного значения (то есть >= value). Upper bound возвращает индекс первого элемента, который строго больше заданного значения.

Как они работают?

В стандартном бинарном поиске мы ищем точное совпадение. В lower bound мы продолжаем поиск в левой части, даже если нашли элемент, чтобы найти самое левое вхождение. В upper bound мы ищем первый элемент, который больше target, сдвигая левую границу при равенстве.

Пример кода на JavaScript

function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

function upperBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
}

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

• Поиск диапазона вхождений элемента в отсортированном массиве.
• Реализация бинарного поиска в STL (C++), Python (bisect), Java (Arrays.binarySearch).
• Задачи на подсчет количества элементов в интервале.

Вывод: Lower bound и upper bound — это мощные инструменты для работы с отсортированными данными, позволяющие эффективно находить границы и диапазоны. Их стоит применять везде, где требуется быстрый поиск позиций вставки или подсчет элементов в интервале.