Buscando em uma lista
- Searching significa encontrar se um valor está em uma lista, e onde.
- A resposta usual é o índice do valor, ou
-1se estiver ausente. - Dois métodos clássicos são busca linear e busca binária.
Busca linear
- Verifique cada item por vez, do início.
- Pare assim que encontrar uma correspondência.
- Funciona em qualquer lista, ordenada ou não.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Busca binária
- Busca binária precisa de uma lista ordenada.
- Olhe para o item do meio. Se for o alvo, pare.
- Se o alvo for menor, busque na metade esquerda; se maior, na direita.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Compare-os
- Busca linear pode verificar todos os itens — lenta para listas longas.
- Busca binária descarta metade da lista a cada passo, então é muito mais rápida.
- Mas busca binária só funciona se os dados já estiverem ordenados.
Em pseudocódigo do Cambridge
- Note
DIVé divisão inteira (a//do Python). - Arrays do Cambridge geralmente variam de 1 a
n, o número de itens.LENGTH()é para strings, então os laços usamn.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
Erros comuns
- Busca binária precisa de uma lista ordenada; ela divide o intervalo pela metade a cada passo.
- Busca linear funciona em qualquer lista mas é mais lenta.
Agora você tenta
- Retorne o índice do valor, ou
-1quando não for encontrado. - Clique em Check answer para testar seu código.
Busca linear vs busca binária
A busca binária metade a lista a cada passo — muitas menos comparações.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Escreva linear_search(items, target) que retorna o índice de target em items, ou -1 se não estiver lá. Verifique os itens um por um.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Escreva binary_search(items, target) para uma lista ordenada. Retorne o índice de target, ou -1 se estiver ausente. Metade o intervalo a cada passo.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Escreva first_negative(items) que varre a lista e retorna o índice do primeiro número menor que 0, ou -1 se não houver nenhum.
Clique em Executar para ver a saída aqui.