Що таке експоненційний пошук (exponential search)?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Експоненційний пошук (exponential search) - це алгоритм пошуку у відсортованому масиві, який спочатку експоненційно розширює робочий діапазон (1, 2, 4, 8, ...), поки не "перестрибне" цільовий елемент, а потім виконує бінарний пошук усередині знайденого діапазону. Час роботи - O(log i), де i - позиція шуканого елемента; у найгіршому випадку - O(log n). Потребує довільного доступу та відсортованості даних.

Детальний розбір

Ідея алгоритму

Якщо масив відсортований за зростанням, можна швидко "оцінити" приблизний діапазон, де може перебувати елемент. Для цього ми перевіряємо індекси, що зростають експоненційно: 1, 2, 4, 8, ... Зупиняємось, коли зустріли елемент, не менший за цільовий, або вийшли за межі масиву. Після цього запускаємо звичайний бінарний пошук усередині цього діапазону.

Кроки алгоритму

Перевірити перший елемент: якщо дорівнює цілі - повернути індекс 0.
Ініціалізувати bound = 1 і подвоювати: 1, 2, 4, 8, … поки bound < n і arr[bound] < target.
Визначити межі для бінарного пошуку: left = bound / 2 (округлення вниз), right = min(bound, n - 1).
Виконати бінарний пошук у [left, right]. Знайти індекс або повернути -1, якщо елемента немає.

Складність

Час: O(log i), де i - індекс цілі; у найгіршому випадку O(log n). Експоненційний етап - O(log i), бінарний етап - O(log i).
Пам'ять: O(1) додаткової пам'яті.

Коли застосовувати

Відсортовані масиви зі швидким довільним доступом (наприклад, звичайні масиви в пам'яті).
Структури, де довжина невідома заздалегідь або логічно "нескінченна" (наприклад, інтерфейси доступу, що повертають значення за індексом, але не дають розмір; часто трапляється в задачах на співбесідах).
Сценарії, коли ціль передбачається "близько до початку" - експоненційне зростання швидко локалізує невеликий діапазон.

Переваги та обмеження

Плюси: швидше локалізує діапазон порівняно з лінійним пошуком; не потребує знання довжини масиву; теоретично може бути ефективнішим за звичайний бінарний, якщо ціль перебуває близько до початку (менший логарифм від i, а не від n).
Мінуси: потребує відсортованості та довільного доступу; на структурі з дорогим доступом за індексом (наприклад, зв'язані списки) незастосовний; при множинних повторах повертає довільний індекс, якщо не модифікувати бінарний етап для пошуку лівої межі.

Приклад коду (JavaScript)

function exponentialSearch(arr, target) {
  const n = arr.length;
  if (n === 0) return -1;
  if (arr[0] === target) return 0;

  // Експоненційне розширення діапазону
  let bound = 1;
  while (bound < n && arr[bound] < target) {
    bound *= 2;
  }

  const left = Math.floor(bound / 2);
  const right = Math.min(bound, n - 1);
  return binarySearchInRange(arr, target, left, right);
}

function binarySearchInRange(arr, target, left, right) {
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] === target) return mid; // Для першої позиції див. варіант нижче
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// Варіант, що повертає індекс ПЕРШОГО входження при дублікатах
function binarySearchFirst(arr, target, left, right) {
  let ans = -1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] >= target) {
      if (arr[mid] === target) ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
}

// Приклад використання:
// const idx = exponentialSearch([1,3,5,7,9,12,15,18,21], 12); // => 5

Покроковий приклад

Масив: [1, 3, 5, 7, 9, 12, 15, 18, 21, 24, 27, 30], ціль: 18.

Перевіряємо arr[0] = 1 ≠ 18.
bound = 1: arr[1] = 3 < 18 → bound = 2.
bound = 2: arr[2] = 5 < 18 → bound = 4.
bound = 4: arr[4] = 9 < 18 → bound = 8.
bound = 8: arr[8] = 21 ≥ 18 → діапазон знайдено: [left = 4, right = 8].
Бінарний пошук у [4, 8]: mid = 6 → arr[6] = 15 < 18 → left = 7; mid = 7 → arr[7] = 18 → знайдено, індекс 7.

Варіації та практичні поради

Для масивів з дублікатами використовуйте бінарний пошук лівої/правої межі, щоб повернути перше/останнє входження.
Якщо порядок спадний, інвертуйте умови порівнянь на обох етапах.
При невідомому розмірі колекції використовуйте безпечний доступ з обробкою виходу за межі (наприклад, API може повертати +∞/undefined при зверненні за межі). Подвоюйте bound до "сигналу" виходу, потім бінарний пошук в останньому валідному діапазоні.

Перевірка крайових випадків

Порожній масив → повернути -1.
Ціль менша за перший елемент → бінарний етап у вузькому діапазоні [0, 0].
Ціль більша за всі елементи → right буде n - 1; бінарний етап коректно поверне -1.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.