Sammenligninger
Fund
Tilbage at tjekke

  • Mål
  • Sammenlignet
  • Udelukket
  • Fundet

Mere om lineær søgning

Lineær søgning

Lineær søgning er den enkleste måde at finde en værdi på: start fra begyndelsen og tjek hver værdi efter tur, indtil den dukker op. Den virker på enhver liste, sorteret eller ej. Vælg den værdi, du leder efter, afspil søgningen eller gå igennem den én sammenligning ad gangen, og se, hvordan prisen afhænger af, hvor værdien står, eller om den overhovedet er der. Tryk på Afspil for at se søgningen, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe hvorhen du vil. Den stiplede linje markerer den værdi, du søger efter. Vælg værdien, hvor mange søjler, hvordan de starter, eller skriv dine egne tal. Slå Stop ved første fund fra for at finde alle fund. Når brættet er valgt, går piletasterne et trin, mellemrumstasten afspiller og sætter på pause, og Home og End hopper til starten og slutningen.

Sådan virker det

  1. Vælg den værdi, du vil søge efter, hvor mange søjler og hvordan de starter. Eller skriv dine egne tal.
  2. Tryk på Afspil, eller brug Trin og Tilbage for at gå én sammenligning ad gangen. Træk i trinskyderen for at hoppe til et vilkårligt sted i søgningen.
  3. Slå Stop ved første fund fra for at tjekke hver værdi og finde alle fund.

Sådan virker lineær søgning

Sammenlign den første værdi med målværdien. Er de ens, er du færdig. Hvis ikke, så gå videre til den anden værdi, så den tredje og så videre. Når du når slutningen af listen uden et fund, er målværdien ikke i listen. Der er intet at forberede: listen behøver ikke at være sorteret.

Hvor mange sammenligninger

En værdi på plads k findes efter k sammenligninger. Det bedste tilfælde er én sammenligning, når målværdien står først. Det værste tilfælde er n, når den står sidst eller mangler, for først når du har tjekket hver værdi, kan du være sikker på, at den ikke er der. I gennemsnit kræver en værdi, der er i listen, omkring (n + 1)/2. For en sorteret liste klarer binær søgning sig langt bedre: omkring log₂ n sammenligninger, 6 i stedet for op til 40 ved 40 værdier.

Ofte stillede spørgsmål

Hvordan virker lineær søgning?

Den tjekker en listes værdier én ad gangen, fra den første til den sidste, indtil den finder målværdien eller løber tør for værdier. Den kaldes også sekventiel søgning.

Hvad er tidskompleksiteten for lineær søgning?

O(n): i det værste tilfælde, når målværdien står sidst eller mangler, sammenligner den målværdien med alle n værdier. I gennemsnit kræver en målværdi, der er i listen, omkring (n + 1)/2 sammenligninger.

Hvornår er lineær søgning et godt valg?

Til korte lister, til lister, der ikke er sorterede og kun gennemsøges en eller to gange, og til data, du kun kan læse i rækkefølge, som en strøm. Det betaler sig kun at sortere først, så binær søgning kan bruges, hvis du søger mange gange.

Hvorfor koster en manglende værdi mest?

Fordi intet fortæller lineær søgning, at den kan stoppe tidligt. Et fund kan kun udelukkes ved at tjekke hver værdi, så en værdi, der ikke er i listen, kræver altid n sammenligninger.

Bliver mine tal sendt nogen steder hen?

Nej. Søgningen kører i din browser, og dine seneste indstillinger gemmes i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor