Binær søgning vs lineær søgning
Lineær søgning, også kendt som sekventiel søgning, er den enkleste søgealgoritme. Det søger efter en specificeret værdi på en liste ved at kontrollere hvert element på listen. Binær søgning er også en metode, der bruges til at lokalisere en specificeret værdi i en sorteret liste. Binær søgemetode halverer antallet af kontrollerede elementer (i hver iteration), hvilket reducerer den tid, det tager at finde det givne element på listen.
Hvad er lineær søgning?
Lineær søgning er den enkleste søgemetode, som kontrollerer hvert element i en liste sekventielt, indtil det finder et bestemt element. Input til den lineære søgemetode er en sekvens (såsom en matrix, samling eller en streng) og det element, der skal søges. Outputtet er sandt, hvis det angivne element ligger inden for den angivne sekvens eller falsk, hvis det ikke er i sekvensen. Da denne metode kontrollerer hvert element på listen, indtil det angivne element er fundet, vil det i værste fald gennemgå alle elementerne på listen, før det finder det nødvendige element. Kompleksiteten af lineær søgning er o (n). Derfor anses det for at være for langsomt til at blive brugt, når man søger i elementer i store lister. Men dette er meget simpelt og lettere at implementere.
Hvad er binær søgning?
Binær søgning er også en metode, der bruges til at lokalisere et bestemt element i en sorteret liste. Denne metode starter med at sammenligne det søgte element med elementerne i midten af listen. Hvis sammenligningen bestemmer, at de to elementer er ens, stopper metoden og returnerer elementets position. Hvis det søgte element er større end det midterste element, starter metoden igen ved kun at bruge den nederste halvdel af den sorterede liste. Hvis det søgte element er mindre end det midterste element, starter metoden igen ved kun at bruge den øverste halvdel af den sorterede liste. Hvis det søgte element ikke er på listen, returnerer metoden en unik værdi, der indikerer det. Derfor halverer den binære søgemetode antallet af sammenlignede elementer (i hver iteration) afhængigt af resultatet af sammenligningen. Følgelig,binær søgning kører i logaritmisk tid, hvilket resulterer i o (log n) gennemsnitlig sagsydelse.
Hvad er forskellen mellem binær søgning og lineær søgning?
Selvom både lineær søgning og binær søgning er søgemetoder, har de flere forskelle. Mens binær søgning fungerer på sorterede lister, kan linjesøgning også fungere på usorterede lister. Sortering af en liste har generelt en gennemsnitlig sagskompleksitet på n log n. lineær søgning er enkel og ligetil at implementere end den binære søgning. Men lineær søgning er for langsom til at blive brugt med store lister på grund af dens o (n) gennemsnitlige sagspræstation. På den anden side anses binær søgning for at være en mere effektiv metode, der kan bruges med store lister. Men at implementere den binære søgning kan være ret vanskelig, og en undersøgelse har vist, at den nøjagtige kode til binær søgning kun kunne findes i fem ud af tyve bøger.
