Forskellen mellem binær søgning og lineær søgning

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 på en liste ved at kontrollere hvert element på listen. Binær søgning er også en metode, der bruges til at finde 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, der kontrollerer hvert element i en liste sekventielt, indtil det finder et specificeret element. Input til den lineære søgemetode er en sekvens (f.eks. En matrix, samling eller en streng) og det element, der skal søges. Outputet er sandt, hvis den specificerede vare er inden for den angivne sekvens eller falsk, hvis den ikke er i sekvensen. Da denne metode kontrollerer hvert element på listen, indtil det specificerede element er fundet, går det i værste tilfælde gennem alle elementerne på listen, før det finder det krævede element. Kompleksiteten ved lineær søgning er o (n). Derfor betragtes det som for langsomt til at blive brugt, når man søger efter elementer i store lister. Men dette er meget enkelt og lettere 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 ved kun at bruge den nederste halvdel af den sorterede liste. Hvis det søgte element er mindre end det midterste element, starter det 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 kører binær søgning i logaritmisk tid, hvilket resulterer i o (log n) gennemsnitlig sagspræstation.

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 sagsresultater. På den anden side betragtes binær søgning som en mere effektiv metode, der kunne bruges med store lister. Men implementering af den binære søgning kunne være ganske 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.