Алгоритмы: поиск
Что мы сделаем
- Алгоритм — это чёткий список шагов, решающих задачу.
- Очень частая задача — поиск: найти, где значение находится в списке.
- Мы изучим два алгоритма: линейный поиск и бинарный поиск.
Линейный поиск
- Проверяйте элементы один за другим, от начала до конца.
- Если вы нашли значение, верните его индекс (позицию).
- Если вы достигли конца и так ничего не нашли, верните
-1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
print(linear_search([4, 8, 15, 16], 15))
print(linear_search([4, 8, 15, 16], 99))
Почему отсортированный список помогает
- Линейный поиск работает с любым списком, даже беспорядочным.
- Но если список отсортирован (от меньшего к большему), мы можем работать значительно быстрее.
- Бинарный поиск использует порядок сортировки, чтобы на каждом шаге отбрасывать половину списка.
Бинарный поиск
- Посмотрите на средний элемент.
- Если это целевое значение, вы закончили.
- Если целевое значение меньше, ищите в левой половине; если больше, в правой. Повторяйте.
def binary_search(sorted_lst, target):
low = 0
high = len(sorted_lst) - 1
while low <= high:
mid = (low + high) // 2
if sorted_lst[mid] == target:
return mid
elif sorted_lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([1, 3, 5, 7, 9], 4))
Объединение идей
- Поиск объединяет три базовых блока, которые вы уже знаете.
- Последовательность: выполняйте шаги по порядку. Выбор:
if/elif/else. - Итерация: цикл (
forилиwhile) повторяет проверку.
Псевдокод в AP CSP
- На экзамене пишут цикл и проверку вот так.
FOR EACHпосещает каждый элемент;IFвыбирает;REPEAT UNTILциклически повторяет, пока условие не станет истинным.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Распространенные ошибки
- Бинарный поиск требует отсортированного списка.
- Линейный поиск проверяет каждый элемент по очереди.
Теперь попробуйте сами
- Каждое задание содержит название процедуры и то, что она должна возвращать.
- Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Поиск в списке
Бинарный поиск требует отсортированного списка, но работает значительно быстрее линейного.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру linear_search(lst, target). Верните индекс элемента ⟨target⟩ в списке lst, или верните ⟨-1⟩, если его там нет. Проверяйте элементы по очереди.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру binary_search(sorted_lst, target) для списка, отсортированного от меньшего к большему. Верните индекс элемента ⟨target⟩, или верните ⟨-1⟩. Смотрите на средний элемент и сокращайте область поиска вдвое каждый раз.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Напишите процедуру contains(lst, target), которая возвращает ⟨True⟩, если ⟨target⟩ содержится в списке lst, иначе возвращает ⟨False⟩. Вы можете переиспользовать линейный поиск и сравнить результат с ⟨-1⟩.
Нажмите Запустить, чтобы увидеть результат здесь.