Lineær søgning algoritme

Lineær søgning er den enkleste måde at finde noget i en liste på: man går elementerne igennem ét ad gangen fra start, til man finder det, man leder efter — eller når til enden. Den kaldes også sekventiel søgning og er typisk den første søgealgoritme, man støder på i programmering.

Det svarer til at lede efter en bestemt bog på en uordnet reol ved at kigge på hver eneste ryg, til du rammer den rigtige.

Styrken — og svagheden

Fordelen er enkelhed: listen behøver ikke være sorteret på forhånd, og metoden virker på stort set enhver form for liste. Det gør den ideel til små datamængder eller data, hvor du ikke kender strukturen.

Svagheden er hastigheden. Jo længere listen er, jo længere tid tager det — og i værste fald (når elementet ligger sidst eller slet ikke findes) skal hele listen gennemgås. På en liste med en million elementer er det en million sammenligninger.

Når listen vokser

Til store, sorterede datamængder bruger man i stedet hurtigere metoder som binær søgning, der halverer søgeområdet for hvert trin og dermed finder elementet langt færre skridt. Hvor lineær søgning skal gennem en million elementer, klarer binær søgning det samme på cirka tyve sammenligninger.

Pointen er ikke, at den ene altid slår den anden. Lineær søgning er hurtig nok — og ofte det rigtige valg — så længe datamængden er lille, eller dataene ikke er sorteret.