Binær søgning vs Lineær søgning
Lineær søgning, også kendt som sekventiel søgning, er den enkleste søgealgoritme. Den søger efter en specificeret værdi i 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 specificeret element. Inputtet til den lineære søgemetode er en sekvens (såsom en matrix, samling eller en streng) og det element, der skal søges i. Outputtet er sandt, hvis det angivne element er 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 den i værste fald gennemgå alle elementerne på listen, før den finder det nødvendige element. Kompleksiteten af lineær søgning er o(n). Derfor anses den for at være for langsom til at blive brugt, når der søges efter elementer i store lister. Men dette er meget enkelt og nemmere at implementere.
Hvad er binær søgning?
Binær søgning er også en metode, der bruges til at finde et specificeret 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 det metoden igen med kun den nederste halvdel af den sorterede liste. Hvis det søgte element er mindre end det midterste element, starter det metoden igen med kun den øverste halvdel af den sorterede liste. Hvis det søgte element ikke er på listen, vil metoden returnere 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. Som følge heraf kører binær søgning i logaritmisk tid, hvilket resulterer i o(log n) gennemsnitlig caseydelse.
Hvad er forskellen mellem binær søgning og lineær søgning?
Selv om 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 linersø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 sagsydelse. På den anden side anses binær søgning for at være en mere effektiv metode, der kunne bruges med store lister. Men implementeringen af den binære søgning kunne 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.
