какой алгоритм даст мне O (logd)

Question

вопрос: «Предложите алгоритм, который принимает отсортированный массив и X, и он вернет индекс X в массиве, если он не найден в массиве, возвращающем -1, временная сложность алгоритма должна быть O (log d) хотя d - это количество элементов, которые меньше, чем X

Я не могу думать о чем-то другом, кроме как посмотреть на средний индекс и сравнить его, если он меньше или больше, чем X, затем сделать то же самое рекурсивно... но я не думаю, что это O (журнал d). У меня есть домашнее задание, и я не знаю, что делать.

Answer 1

Экспоненциальный поиск равен O (log d) .

Начиная с upper = 0, сравните значение array[upper] с value. Если оно меньше value, обновите upper = (upper + 1) * 2; до array[upper] >= value. Если оно равно, вернуть upper, в противном случае выполнить бинарный поиск между [upper / 2, upper).

В JavaScript это будет выглядеть так:

function exponentialSearch (array, value) {
  let upper = 0;
  // exponential gallop
  while (array[upper] < value) upper = (upper + 1) * 2;

  if (array[upper] === value) return upper;
  // binary search
  for (let lower = upper / 2; upper > lower; ) {
    const bisect = lower + Math.floor((upper - lower) / 2);

    if (array[bisect] > value) upper = bisect;
    else if (array[bisect] < value) lower = bisect;
    else return bisect;
  }

  return -1;
}