Lineær søgning
Lineær søgning er det, du gør, når du leder efter et navn på en usorteret liste: start øverst og læs nedad, indtil du finder det. Det er den enkleste søgning, der findes, den virker på enhver liste, og til korte lister er den ofte alt, hvad du har brug for.
Idéen
Sammenlign målværdien med listens første værdi. Er de ens, så stop: målværdien er på plads 1. Ellers sammenlign den med den anden værdi, så den tredje og så videre. Hvis heller ikke den sidste værdi passer, er målværdien ikke i listen. Du behøver ikke at vide noget om listen på forhånd: den behøver ikke at være sorteret, og værdierne kan være hvad som helst, der kan sammenlignes for lighed.
Et eksempel
Søg efter 4 i 5, 1, 4, 2, 8. Er 5 lig med 4? Nej. Er 1? Nej. Er 4? Ja: fundet på plads 3 efter 3 sammenligninger. Søg nu efter 7 i den samme liste. Hver af de fem værdier tjekkes, og ingen passer, så efter 5 sammenligninger er svaret, at 7 ikke er der.
Hvor mange sammenligninger
En værdi på plads k kræver k sammenligninger at finde. Hvis målværdien er lige sandsynlig på hver plads, er det (n + 1)/2 sammenligninger i gennemsnit: 20,5 ved 40 værdier. En manglende værdi kræver altid n, for først efter den sidste sammenligning er det sikkert, at ingen værdi passede. Prisen vokser altså proportionalt med listens længde, hvilket skrives O(n).
Hurtigere søgning kræver orden
Lineær søgning kan ikke springe noget over, for i en usorteret liste kan enhver værdi stå hvor som helst. Når en liste er sorteret, fortæller en sammenligning mere end ens eller ej: den fortæller, på hvilken side målværdien er. Binær søgning bruger det til at halvere listen ved hvert trin og kræver omkring log₂ n sammenligninger, højst 6 ved 40 værdier. Sortering koster dog også tid, så for en liste, der kun gennemsøges én gang, er lineær søgning ofte det bedre valg.
Små forbedringer
En version med vagtpost sætter målværdien sidst i listen før søgningen, så løkken kun skal teste for et fund og ikke også for listens slutning. At flytte en værdi én plads frem, eller helt forrest, hver gang den findes, gør ofte søgte værdier billigere over tid. Ingen af delene ændrer det værste tilfælde på n sammenligninger.
Udforsk den
Åbn appen, vælg en værdi i Søg efter, og tryk på Trin. Den stiplede linje viser målværdiens højde, hver værdi fremhæves, mens den tjekkes, og falmer, når den er udelukket, og et fund bliver grønt. Søg efter en værdi, der ikke er i listen, for at se et fuldt gennemløb, eller slå Stop ved første fund fra, og brug få unikke værdier for at finde flere fund.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for lineær søgning?
O(n) i det værste og det gennemsnitlige tilfælde, og O(1) i det bedste tilfælde, når målværdien er den første værdi. Den kræver ingen ekstra hukommelse.
Hvad er forskellen på lineær søgning og binær søgning?
Lineær søgning tjekker hver værdi i rækkefølge og virker på enhver liste. Binær søgning virker kun på en sorteret liste, men halverer ved hvert trin den del, der kan indeholde målværdien, så den kræver omkring log₂ n sammenligninger i stedet for op til n.
Kræver lineær søgning en sorteret liste?
Nej. Det er dens største fordel. På en sorteret liste kan den stoppe, så snart den passerer den plads, hvor målværdien ville stå, men den er stadig langsommere end binær søgning.
Hvor bruges lineær søgning?
Overalt, hvor lister er korte eller usorterede: at finde et element i et lille array, at gennemløbe en fil eller en strøm, der kun kan læses i rækkefølge, eller at tjekke hvert element for en betingelse. Mange biblioteksfunktioner, såsom indexOf i JavaScript og list.index i Python, er lineære søgninger.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv lineær søgning