👩‍💻👩‍💻 Как выглядит алгоритм экспотенциального поиска на JavaScript?

Экспоненциальный поиск позволяет выполнять поиск по отсортированному неограниченному списку для указанного входного значения (поисковый «ключ»)

Алгоритм состоит из двух этапов. Первый этап определяет диапазон, в котором ключ поиска находился бы, если бы он был в списке. На втором этапе выполняется бинарный поиск по этому диапазону

❗️ В нашем примере binarySearchIterative - это функция бинарного поиска, про который мы уже писали раньше

export const exponentialSearch = (
  array: number[],
  x: number
): number | null => {
  const arrayLength = array.length
  if (arrayLength === 0) return null

  if (array[0] === x) return 0

  let i = 1
  while (i < arrayLength && array[i] <= x) {
    i = i * 2
  }

  const start = Math.floor(i / 2)
  const end = Math.min(i, arrayLength - 1)
  const result = binarySearchIterative(array, x, start, end)

  return result
}

Coderoll | Frontend