Söka och sortera — snabbt eller långsamt?
Kunna jämföra att leta igenom allt med att söka i en sorterad lista.
Förkunskaper
- BAlgoritmiskt tänkandekrävs
Intuition
Du ska hitta ett namn i en lista med 1 000 namn.
Osorterad lista: du måste titta på ett i taget. I värsta fall 1 000 kollar. Det kallas linjär sökning.
Sorterad lista: slå upp mitten. Är namnet före eller efter? Släng halva listan. Upprepa. Det kallas binärsökning — och tar bara 10 kollar för 1 000 namn.
Därför lönar det sig nästan alltid att sortera först, om man ska söka många gånger.
Interaktivt
Räkna halveringarna: hur många gånger kan du halvera 1 000 innan du är nere på 1?
1 000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Tio steg.
| Antal | Linjärt (värsta fall) | Binärt |
|---|---|---|
| 10 | 10 | 4 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
En miljon namn på tjugo kollar. Det är därför telefonkataloger, ordböcker och databasindex är sorterade.
Gissningsleken: «jag tänker på ett tal mellan 1 och 100». Gissa alltid mitten (50, sedan 25 eller 75 …) så hittar du det på högst sju gissningar — varje gång.
Behärskning innebär
- Jämför linjär sökning med binärsökning
- Uppskattar hur många steg som behövs i en sorterad lista
Logga in för att göra övningarna och bygga upp din behärskning.
Källor
- CS Unplugged (CC BY-SA 4.0) — CC BY-SA 4.0
- Wikipedia — Binärsökning (CC BY-SA 4.0) — CC BY-SA 4.0