Sökstrategier: linjär sökning kontra binärsökning
Kunna jämföra kostnaden för att leta igenom en osorterad lista med att söka i en sorterad lista.
Intuition
Du ska hitta en specifik kund i en lista med 1 000 namn.
Osorterad lista: Du måste kontrollera ett namn i taget. I värsta fall krävs 1 000 kontroller. Detta kallas linjär sökning.
Sorterad lista: Du börjar i mitten. Är namnet före eller efter? Då kan du utesluta halva listan. Upprepa processen. Detta kallas binärsökning — och kräver bara 10 kontroller för 1 000 namn.
Därför är det oftast effektivt att sortera data först, om du ska söka i datamängden 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 poster | Linjär sökning (värsta fall) | Binär sökning |
|---|---|---|
| 10 | 10 | 4 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
En miljon poster på tjugo kontroller. Det är anledningen till att telefonkataloger, ordböcker och databasindex är sorterade.
Exempel på strategin: Tänk dig att du ska hitta ett tal mellan 1 och 100. Om du alltid väljer mitten (50, sedan 25 eller 75 …) hittar du talet på högst sju steg — 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
Förkunskaper
- BAlgoritmiskt tänkandekrävs
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