10,3 тыс подписчиков
🖥 Задача реализовать экспоненциального поиска.
Экспоненциальный поиск — это еще один алгоритм поиска, который может быть достаточно легко реализован на Python, по сравнению с jump search и поиском Фибоначчи, которые немного сложны. Он также известен под названиями galloping search, doubling search и Struzik search.
Экспоненциальный поиск зависит от бинарного поиска для выполнения окончательного сравнения значений. Алгоритм работает следующим образом:
Определяется диапазон, в котором, скорее всего, будет находиться искомый элемент.
В этом диапазоне используется двоичный поиск для нахождения индекса элемента.
Решение
Реализация алгоритма экспоненциального поиска на Python:
def ExponentialSearch(lys, val):
if lys[0] == val:
return 0
index = 1
while index < len(lys) and lys[index] <= val:
index = index * 2
return BinarySearch( lys[:min(index, len(lys))], val)
Используем функцию, чтобы найти значение:
>>> print(ExponentialSearch([1,2,3,4,5,6,7,8],3))
Рассмотрим работу алгоритма пошагово.
Проверяем, соответствует ли первый элемент списка искомому значению: поскольку lys[0] равен 1, а мы ищем 3, мы устанавливаем индекс равным 1 и двигаемся дальше.
Перебираем все элементы в списке, и пока элемент с текущим индексом меньше или равен нашему значению, умножаем значение индекса на 2:
index = 1, lys[1] равно 2, что меньше 3, поэтому значение index умножается на 2 и переменной index присваивается значение 2.
index = 2, lys[2] равно 3, что равно 3, поэтому значение index умножается на 2 и переменной index присваивается значение 4.
index = 4, lys[4] равно 5, что больше 3. Условие выполнения цикла больше не соблюдается и цикл завершает свою работу.
Затем выполняется двоичный поиск в полученном диапазоне (срезе) lys[:4]. В Python это означает, что подсписок будет содержать все элементы до 4-го элемента, поэтому мы фактически вызываем функцию следующим образом:
>>> BinarySearch([1,2,3,4], 3)
Функция вернет следующий результат:
2
Этот результат является индексом искомого элемента как в исходном списке, так и в срезе, который мы передаем алгоритму бинарного поиска.
Экспоненциальный поиск выполняется за время O(log i), где i — индекс искомого элемента. В худшем случае временная сложность равна O(log n), когда искомый элемент — это последний элемент в массиве (n — это длина массива).
Экспоненциальный поиск работает лучше, чем бинарный, когда искомый элемент находится ближе к началу массива. На практике мы используем экспоненциальный поиск, поскольку это один из наиболее эффективных алгоритмов поиска в неограниченных или бесконечных массивах.
👉 Пишите ваше решение в комментариях👇
2 минуты
24 марта 2023
202 читали