Экспоненциальный поиск или Finger Search

Finger Search ищет элемент в отстортированном массиве, перескакивая 2 ^ i элеентов на каждой итерации, где i представляет значение переменной управления циклом. После идет проверка: присутствует ли элемент поиска между последним и текущим переходом.

Как это работает?

1. Проходите по элементам массива по 2 ^ i за один раз, выполняя поиск условия:

Array[2 ^ (i - 1)] < valueWanted < Array[ 2 ^ i]


Если 2 ^ i больше, чем длина массива, установите верхнюю границу равной длине массива

2. Выполните двоичный поиск между массивами


Array[2 ^ (i - 1)] и Array[2 ^ i]

Data Science: Алгоритмы и Структуры данных | Чат 💬