🖥 Задача реализовать экспоненциального поиска. Экспоненциальный поиск — это еще один алгоритм поиска, который может быть достаточно легко реализован на 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 — это длина массива). Экспоненциальный поиск работает лучше, чем бинарный, когда искомый элемент находится ближе к началу массива. На практике мы используем экспоненциальный поиск, поскольку это один из наиболее эффективных алгоритмов поиска в неограниченных или бесконечных массивах. 👉 Пишите ваше решение в комментариях👇 @machinelearning