algoritmy_poisk_prezentaciya

1.

Алгоритмы поиска
Экспоненциальный, тернарный и интерполяционный
Кратко: как работают и как выглядят в Python
Небольшая презентация по информатике

2.

1. Что такое алгоритм поиска?
Это способ найти нужное значение в списке.
Например, есть список:
[3, 7, 12, 18, 25, 31]
Нужно найти число 18.
У разных алгоритмов разные идеи:
• один расширяет границы поиска;
• другой делит отрезок на части;
• третий оценивает, где число может
находиться.
Важно: все три алгоритма обычно применяют к отсортированному списку.
2

3.

2. Экспоненциальный поиск
Идея
Сначала быстро увеличиваем правую границу:
1, 2, 4, 8… Когда нужное число уже может быть
внутри, запускаем бинарный поиск.
Сложность: O(log n)
Список должен быть отсортирован.
def exponential_search(a, x):
if not a:
return -1
if a[0] == x:
return 0
i = 1
while i < len(a) and a[i] < x:
i *= 2
left = i // 2
right = min(i, len(a) - 1)
return binary_search(a, x, left, right)
В коде используется вспомогательная функция binary_search.
3

4.

3. Тернарный поиск
Идея
Отрезок делится примерно на три части.
Сравниваем число с двумя точками и
оставляем только нужную часть.
def ternary_search(a, x):
left, right = 0, len(a) - 1
while left <= right:
third = (right - left) // 3
m1 = left + third
m2 = right - third
Сложность: O(log n)
Подходит для отсортированного списка.
if a[m1] == x:
return m1
if a[m2] == x:
return m2
if x < a[m1]:
right = m1 - 1
elif x > a[m2]:
left = m2 + 1
else:
left, right = m1 + 1, m2 - 1
return -1
4

5.

4. Интерполяционный поиск
Идея
Он не всегда берёт середину. По значениям
на концах оценивает, где примерно может
стоять искомое число. Особенно хорошо
работает на равномерно распределённых
числах.
def interpolation_search(a, x):
low, high = 0, len(a) - 1
while low <= high and a[low] <= x <= a[high]:
if a[low] == a[high]:
return low if a[low] == x else -1
pos = low + int(
(x - a[low]) * (high - low) /
(a[high] - a[low])
)
В среднем: O(log log n) для равномерных данных.
В худшем случае: O(n).
if a[pos] == x:
return pos
if a[pos] < x:
low = pos + 1
else:
high = pos - 1
return -1
5

6.

5. Сравнение алгоритмов
Алгоритм
Как ищет
Сложность
Экспоненциальный
Удваивает границу, затем бинарный поиск
O(log n)
Тернарный
Делит диапазон на 3 части
O(log n)
Интерполяционный
Оценивает позицию по значениям
Средняя O(log log n), худшая O(n)
Возвращаем индекс найденного элемента, а если его нет — -1.
6

7.

6. Пример и вывод
Пример использования
numbers = [3, 7, 12, 18, 25, 31]
target = 18
# Пример для тернарного поиска
result = ternary_search(numbers, target)
print(result) # 3
Коротко
• Все алгоритмы ищут элемент в
отсортированном списке.
• Универсально быстрее не значит: выбор
зависит от данных.
• Для обычных задач часто достаточно
бинарного поиска.
Спасибо за внимание!
7