Forskel 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 den sekventielle søgning er den enkleste søgealgoritme. Den søger efter en bestemt værdi i en liste ved at tjekke hvert element i listen. Binær søgning er også en metode, der bruges til at finde en bestemt værdi på en sorteret liste. Binær søgemetode halverer antallet af kontrollerede elementer (i hver iteration), hvilket reducerer den tid, der er taget for at lokalisere det givne emne i listen.

Hvad er lineær søgning?

Lineær søgning er den enkleste søgemetode, som kontrollerer hvert element i en liste i rækkefølge, indtil den finder et bestemt element. Indgangen til den lineære søgemetode er en sekvens (som en matrix, en samling eller en streng) og det element, der skal søges. Udgangen er sand, hvis det angivne element ligger inden for den angivne rækkefølge eller falsk, hvis den ikke er i sekvensen. Da denne metode kontrollerer hvert element i listen, indtil det angivne element er fundet, vil det i værste fald gennemgå alle elementerne i listen, før det finder det nødvendige element. Kompleksiteten af ​​lineær søgning er o (n). Derfor anses det for langsomt at blive brugt, når man søger elementer i store lister. Men det 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 lokalisere et specificeret emne på en sorteret liste. Denne metode starter ved at sammenligne det søgte element med elementerne midt på 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 mellemelementet, starter det metoden igen med kun den nederste halvdel af den sorterede liste. Hvis det søgte element er mindre end mellemelementet, starter det metoden igen med kun den øverste halvdel af den sorterede liste. Hvis det søgte element ikke er på listen, returnerer metoden en unik værdi, der angiver det. Derfor halverer binær søgemetoden antallet af elementer sammenlignet (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 case performance.

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 søger metoder, har de flere forskelle. Selvom binær søgning fungerer på sorterede lister, kan liner-søgning også fungere på usorterede lister. Sortering af en liste har generelt en gennemsnitskompleksitet af 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 sin o (n) gennemsnitlige case performance.På den anden side betragtes binær søgning som en mere effektiv metode, der kan bruges med store lister. Men gennemførelsen af ​​binær søgning kan være ret vanskelig og en undersøgelse har vist, at den nøjagtige kode for binær søgning kunne findes i kun fem ud af tyve bøger.