Linjär sökning

Linjär sökning är vad du gör när du letar efter ett namn på en osorterad lista: börja högst upp och läs nedåt tills du hittar det. Det är den enklaste sökningen som finns, den fungerar på alla listor, och för korta listor är den ofta allt du behöver.

Staplar i en lista som kontrolleras en i taget från början, de kontrollerade staplarna bleka, en streckad linje i målvärdets höjd och den matchande stapeln markerad
Staplar i en lista som kontrolleras en i taget från början, de kontrollerade staplarna bleka, en streckad linje i målvärdets höjd och den matchande stapeln markerad

Idén

Jämför målvärdet med listans första värde. Om de är lika, stanna: målvärdet finns på plats 1. Annars jämför du det med det andra värdet, sedan det tredje, och så vidare. Om inte heller det sista värdet matchar finns målvärdet inte i listan. Ingenting om listan behöver vara känt i förväg: den behöver inte vara sorterad, och värdena kan vara vad som helst som kan jämföras för likhet.

Ett exempel

Sök efter 4 i 5, 1, 4, 2, 8. Är 5 lika med 4? Nej. Är 1? Nej. Är 4? Ja: hittat på plats 3 efter 3 jämförelser. Sök nu efter 7 i samma lista. Vart och ett av de fem värdena kontrolleras och inget matchar, så efter 5 jämförelser är svaret att 7 inte finns där.

Hur många jämförelser

Ett värde på plats k kräver k jämförelser för att hittas. Om målvärdet är lika sannolikt på varje plats blir det i genomsnitt (n + 1)/2 jämförelser: 20,5 för 40 värden. Ett saknat värde kräver alltid n, eftersom det först efter den sista jämförelsen är säkert att inget värde matchade. Kostnaden växer alltså i proportion till listans längd, vilket skrivs O(n).

Snabbare sökningar kräver ordning

Linjär sökning kan inte hoppa över något, eftersom vilket värde som helst kan finnas var som helst i en osorterad lista. När en lista är sorterad säger en jämförelse mer än lika eller inte: den säger på vilken sida målvärdet finns. Binär sökning använder det för att halvera listan i varje steg och behöver ungefär log₂ n jämförelser, högst 6 för 40 värden. Men sortering tar också tid, så för en lista som bara genomsöks en gång är linjär sökning ofta det bättre valet.

Små förbättringar

En version med vaktpost lägger målvärdet sist i listan före sökningen, så att loopen bara behöver testa för en träff och inte även för listans slut. Att flytta ett värde en plats framåt, eller längst fram, varje gång det hittas gör ofta sökta värden billigare med tiden. Ingen av dem ändrar värsta fallet på n jämförelser.

Utforska den

Öppna appen, välj ett värde i Sök efter och tryck på Steg. Den streckade linjen visar målvärdets höjd, varje värde markeras när det kontrolleras och bleknar när det har uteslutits, och en träff blir grön. Sök efter ett värde som inte finns i listan för att se ett helt varv, eller stäng av Stoppa vid första träffen och använd få unika värden för att hitta flera träffar.

Ofta ställda frågor

Vad är tidskomplexiteten för linjär sökning?

O(n) i värsta fallet och i genomsnitt, och O(1) i bästa fallet, när målvärdet är det första värdet. Den behöver inget extra minne.

Vad är skillnaden mellan linjär sökning och binär sökning?

Linjär sökning kontrollerar varje värde i ordning och fungerar på alla listor. Binär sökning fungerar bara på en sorterad lista, men halverar i varje steg den del som kan innehålla målvärdet, så den behöver ungefär log₂ n jämförelser i stället för upp till n.

Behöver linjär sökning en sorterad lista?

Nej. Det är dess största fördel. På en sorterad lista kan den stanna så snart den passerar platsen där målvärdet skulle stå, men den är ändå långsammare än binär sökning.

Var används linjär sökning?

Överallt där listor är korta eller osorterade: att hitta ett element i en liten array, att gå igenom en fil eller en ström som bara kan läsas i ordning, eller att kontrollera varje element mot ett villkor. Många biblioteksfunktioner, som indexOf i JavaScript och list.index i Python, är linjära sökningar.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova linjär sökning