Algorithms: searching · Algoritmos: busca
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.
O que faremos
- Um algoritmo é uma lista clara de passos que resolve um problema.
- Uma tarefa muito comum é pesquisa: encontrar onde um valor está em uma lista.
- Aprenderemos dois algoritmos: pesquisa linear e pesquisa binária.
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.
Busca linear
- Verifique os itens um por um, do início ao fim.
- Se encontrar o valor, retorne seu índice (posição).
- Se chegar ao final e nunca encontrá-lo, retorne
-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.
Por que uma lista ordenada ajuda
- A pesquisa linear funciona em qualquer lista, mesmo uma bagunçada.
- Mas se a lista estiver ordenada (pequeno para grande), podemos ser muito mais rápidos.
- A pesquisa binária usa a ordem ordenada para pular metade da lista de cada vez.
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.
Busca binária
- Olhe para o item do meio.
- Se for o alvo, você terminou.
- Se o alvo for menor, pesquise na metade esquerda; se maior, na metade direita. Repita.
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.
Juntando as ideias
- Uma pesquisa combina três blocos de construção que você já conhece.
- Sequenciamento: faça os passos em ordem. Seleção:
if/elif/else. - Iteração: um loop (
forouwhile) repete a verificação.
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.
Em pseudocódigo AP CSP
- O exame escreve um loop e uma verificação assim.
FOR EACHvisita todos os itens;IFseleciona;REPEAT UNTILloopa até que um teste seja verdadeiro.
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.
Erros comuns
- Busca binária precisa de uma lista ordenada.
- A pesquisa linear verifica cada item em sequência.
Now you try
- Each task gives a procedure name and what it must return.
- Press Check answer to test your code.
Agora você tenta
- Cada tarefa fornece um nome de procedimento e o que ele deve retornar.
- Clique em Check answer para testar seu código.
Searching a list · Buscando uma lista
Binary search needs a sorted list but is far faster than linear. · Busca binária precisa de uma lista ordenada mas é muito mais rápida que a 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. · Escreva linear_search(lst, target). Retorne o índice de target em lst, ou -1 se não estiver lá. Verifique os itens um por um.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
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. · Escreva binary_search(sorted_lst, target) para uma lista ordenada de pequeno a grande. Retorne o índice de target, ou -1. Olhe para o meio e corte a busca pela metade a cada vez.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write contains(lst, target) that returns True if · se target is in lst, else False. You may reuse linear search and compare the result to -1. · Escreva contains(lst, target) que retorne True se target estiver em lst, senão False. Você pode reutilizar a busca linear e comparar o resultado com -1.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.