Jämförelser
Träffar
Kvar att kontrollera

  • Mål
  • Jämförda
  • Uteslutna
  • Hittade

Mer om linjär sökning

Linjär sökning

Linjär sökning är det enklaste sättet att hitta ett värde: börja från början och kontrollera varje värde i tur och ordning tills det dyker upp. Den fungerar på alla listor, sorterade eller inte. Välj värdet att leta efter, spela upp sökningen eller stega igenom den en jämförelse i taget, och se hur kostnaden beror på var värdet finns, eller om det finns där alls. Tryck på Spela för att se sökningen, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa vart som helst. Den streckade linjen markerar värdet du söker efter. Välj värdet, hur många staplar, hur de börjar, eller skriv dina egna tal. Stäng av Stoppa vid första träffen för att hitta alla träffar. När tavlan är markerad stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Välj värdet att söka efter, antal staplar och startordning. Eller skriv dina egna tal.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå en jämförelse i taget. Dra i stegreglaget för att hoppa var som helst i sökningen.
  3. Stäng av Stoppa vid första träffen för att kontrollera varje värde och hitta alla träffar.

Så fungerar linjär sökning

Jämför det första värdet med målvärdet. Om de är lika är du klar. Om inte, gå vidare till det andra värdet, sedan det tredje, och så vidare. Om du når slutet av listan utan en träff finns målvärdet inte i listan. Det finns inget att förbereda: listan behöver inte vara sorterad.

Hur många jämförelser

Ett värde på plats k hittas efter k jämförelser. Bästa fallet är en jämförelse, när målvärdet är först. Värsta fallet är n, när det är sist eller saknas, eftersom du först efter att ha kontrollerat varje värde kan vara säker på att det inte finns där. I genomsnitt kräver ett värde som finns i listan ungefär (n + 1)/2. För en sorterad lista gör binär sökning det mycket bättre: ungefär log₂ n jämförelser, 6 i stället för upp till 40 för 40 värden.

Ofta ställda frågor

Hur fungerar linjär sökning?

Den kontrollerar värdena i en lista ett i taget, från det första till det sista, tills den hittar målvärdet eller värdena tar slut. Den kallas också sekventiell sökning.

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

O(n): i värsta fallet, när målvärdet är sist eller saknas, jämför den målvärdet med alla n värden. I genomsnitt kräver ett målvärde som finns i listan ungefär (n + 1)/2 jämförelser.

När är linjär sökning ett bra val?

För korta listor, för listor som inte är sorterade och bara genomsöks en eller två gånger, och för data som bara kan läsas i ordning, till exempel en ström. Att sortera först så att binär sökning kan användas lönar sig bara om du söker många gånger.

Varför kostar ett saknat värde mest?

Eftersom ingenting säger åt linjär sökning att stanna tidigt. En träff kan bara uteslutas genom att varje värde kontrolleras, så ett värde som inte finns i listan kräver alltid n jämförelser.

Skickas mina tal någonstans?

Nej. Sökningen körs i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

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

Gå till Editor