Searching & max / min
Esta página precisa de um navegador recente (com suporte a SharedArrayBuffer). Por favor, atualize Chrome, Edge, Firefox ou Safari para a versão mais recente.
English
Linear search
- A linear search looks at each item in turn until it finds the target.
- It is a named standard method in the syllabus.
- Use a loop and remember when you find a match.
English
names = ["Ali", "Bea", "Chen", "Dev"]
target = "Chen"
position = -1 # -1 means "not found yet"
for i in range(len(names)):
if names[i] == target:
position = i
print(position) # 2
positionremembers where the match is. If the target is missing, it stays-1.- Python counts positions from 0, so
"Chen"is at position 2.
Explorar
Linear search, step by step
A linear search checks each item in turn until it finds the target.
English
Finding the maximum
- Start by assuming the first item is the biggest.
- Then check the rest; if one is bigger, remember it instead.
English
scores = [62, 88, 75, 91, 70]
names = ["Ali", "Bea", "Chen", "Dev", "Eli"]
best = scores[0]
best_name = names[0]
for i in range(len(scores)):
if scores[i] > best:
best = scores[i]
best_name = names[i]
print(best_name, best) # Dev 91
i |
scores[i] |
bigger than best? |
best after |
|---|---|---|---|
| 0 | 62 | no (equal) | 62 |
| 1 | 88 | yes | 88 |
| 2 | 75 | no | 88 |
| 3 | 91 | yes | 91 |
| 4 | 70 | no | 91 |
English
Finding the minimum
- The same idea, but keep the smallest value seen so far.
English
temps = [3, -2, 5, -6, 1]
coldest = temps[0]
for t in temps:
if t < coldest:
coldest = t
print(coldest) # -6
- Starting at
temps[0]matters. Startingcoldestat0would still work here, but for a maximum of all-negative values, starting at0gives the wrong answer0.
English
In the exam: standard methods
- Linear search and finding maximum / minimum / average are named in section 7.
Found ← FALSE
FOR I ← 1 TO 4
IF Number[I] = Target
THEN
Found ← TRUE
ENDIF
NEXT I
English
Common mistakes
- Linear search checks each item in turn until it finds the target.
- For max or min, start from the first item, then compare the rest against it.
English
Now you try
- Loop through the list to search or compare.
- Press Check answer to test your code.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Write contains(nums, target) that returns True se target is in the list, using a busca linear loop (do not use the in keyword).
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
The list nums is set. Find the largest value with a loop and store it in biggest (do not use max()).
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Find the smallest value in nums with a loop and store it in smallest (do not use min()).
Clique em Executar para ver a saída aqui.