Searching · Busca
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
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.
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
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)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
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 them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
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.
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
Em pseudocódigo do Cambridge
- Note
DIVé divisão inteira (a//do Python).
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
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.
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
Agora você tenta
- Retorne o índice do valor, ou
-1quando não for encontrado. - Clique em Check answer para testar seu código.
Linear vs binary search · Busca linear vs busca binária
Binary search · Busca binária halves the list each step — far fewer comparisons. · A busca binária metade a lista a cada passo — muitas menos comparações.
Write linear_search(items, target) that returns · decrescentes the index of target in items, or -1 if it is not there. Check the items one by one. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.
Write first_negative(items) that scans the list and returns · decrescentes the index of the first number less than 0, or -1 if there are none. · 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.
Click Run to see the output here. · Clique em Executar para ver a saída aqui.