Algorithms: searching · Алгоритмы: поиск
What we'll do
- An algorithm is a clear list of steps that solves a problem.
- A very common job is searching: find where a value is in a list.
- We will learn two algorithms: linear search and binary search.
Что мы сделаем
- Алгоритм — это чёткий список шагов, решающих задачу.
- Очень частая задача — поиск: найти, где значение находится в списке.
- Мы изучим два алгоритма: линейный поиск и бинарный поиск.
Linear search
- Check the items one by one, from start to end.
- If you find the value, return its index (position).
- If you reach the end and never find it, return
-1.
Линейный поиск
- Проверяйте элементы один за другим, от начала до конца.
- Если вы нашли значение, верните его индекс (позицию).
- Если вы достигли конца и так ничего не нашли, верните
-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))
Why a sorted list helps
- Linear search works on any list, even a messy one.
- But if the list is sorted (small to big), we can be much faster.
- Binary search uses the sorted order to skip half the list each time.
Почему отсортированный список помогает
- Линейный поиск работает с любым списком, даже беспорядочным.
- Но если список отсортирован (от меньшего к большему), мы можем работать значительно быстрее.
- Бинарный поиск использует порядок сортировки, чтобы на каждом шаге отбрасывать половину списка.
Binary search
- Look at the middle item.
- If it is the target, you are done.
- If the target is smaller, search the left half; if bigger, the right half. Repeat.
Бинарный поиск
- Посмотрите на средний элемент.
- Если это целевое значение, вы закончили.
- Если целевое значение меньше, ищите в левой половине; если больше, в правой. Повторяйте.
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))
Putting ideas together
- A search combines three building blocks you already know.
- Sequencing: do steps in order. Selection:
if/elif/else. - Iteration: a loop (
fororwhile) repeats the check.
Объединение идей
- Поиск объединяет три базовых блока, которые вы уже знаете.
- Последовательность: выполняйте шаги по порядку. Выбор:
if/elif/else. - Итерация: цикл (
forилиwhile) повторяет проверку.
In AP CSP pseudocode
- The exam writes a loop and a check like this.
FOR EACHvisits every item;IFselects;REPEAT UNTILloops until a test is true.
Псевдокод в AP CSP
- На экзамене пишут цикл и проверку вот так.
FOR EACHпосещает каждый элемент;IFвыбирает;REPEAT UNTILциклически повторяет, пока условие не станет истинным.
PROCEDURE contains(list, target)
{
FOR EACH item IN list
{
IF (item = target)
{
RETURN(true)
}
}
RETURN(false)
}
Common mistakes
- Binary search needs a sorted list.
- Linear search checks each item in turn.
Распространенные ошибки
- Бинарный поиск требует отсортированного списка.
- Линейный поиск проверяет каждый элемент по очереди.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
Теперь попробуйте сами
- Каждое задание содержит название процедуры и то, что она должна возвращать.
- Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Searching a list · Поиск в списке
Binary search needs a sorted list but is far faster than linear. · Бинарный поиск требует отсортированного списка, но работает значительно быстрее линейного.
Write linear_search(lst, target). Return the index of target in lst, or -1 if it is not there. Check items one by one. · Напишите процедуру linear_search(lst, target). Верните индекс элемента ⟨target⟩ в списке lst, или верните ⟨-1⟩, если его там нет. Проверяйте элементы по очереди.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the index of target, or -1. Look at the middle and cut the search in half each time. · Напишите процедуру binary_search(sorted_lst, target) для списка, отсортированного от меньшего к большему. Верните индекс элемента ⟨target⟩, или верните ⟨-1⟩. Смотрите на средний элемент и сокращайте область поиска вдвое каждый раз.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write contains(lst, target) that returns True if target is in lst, else False. You may reuse linear search and compare the result to -1. · Напишите процедуру contains(lst, target), которая возвращает ⟨True⟩, если ⟨target⟩ содержится в списке lst, иначе возвращает ⟨False⟩. Вы можете переиспользовать линейный поиск и сравнить результат с ⟨-1⟩.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.