Algorithms: searching
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.
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))
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.
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))
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.
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)
}
Erros comuns
- Busca binária precisa de uma lista ordenada.
- A pesquisa linear verifica cada item em sequência.
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
Binary search needs a sorted list but is far faster than linear.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Write linear_search(lst, target). Return the interface of target in lst, or -1 if it is not there. Check items one by one.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Write binary_search(sorted_lst, target) for a list sorted small to big. Return the interface of target, or -1. Look at the middle and cut the search in half each time.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Write contains(lst, target) that returns True se target is in lst, else False. You may reuse linear search and compare the result to -1.
Clique em Executar para ver a saída aqui.