Lineær søgning vs. binær søgning

Indhold

Indhold: Forskel mellem lineær søgning og binær søgning
Sammenligningstabel
Binær søgning
Vigtige forskelle
Konklusion
Forklarende video

Forskellen mellem lineær søgning og en binær søgning er, at i lineær søgning kontrolleres og sammenlignes hvert element og sorteres derefter, mens i binær søgning er en liste, der skal sorteres, opdelt i to dele og derefter sorteret. Søgning og sortering er to hovedkoncepter inden for programmering af computere. Mange algoritmer bruges til søgning og sortering, men de to mest anvendte algoritmer til søgning og sortering er lineær søgning og binær søgning.

Forskellen mellem den lineære søgning og en binær søgning er arbejdet og effektiviteten af begge algoritmer. Binær søgning er en meget mere effektiv algoritme sammenlignet med den lineære søgealgoritme. Iterationen eller den tid det tager at sammenligne hver værdi før sortering er mindre i binær søgning sammenlignet med lineær søgning.

Lineær søgning er en meget kompleks algoritme, hvis du vil søge i et tal på en liste, sammenligne og gentage nogle gange antallet af værdier på listen. Ét efter et hvert element på listen hentes og sammenlignes med det tilstødende element. Alle elementer åbnes og kontrolleres, og så findes det rigtige element. Der kan være det værste tilfælde, hvis det sidste nummer på listen er det nummer, der skal søges. Lineær søgning er den metode, hvorpå arrayet gennemskæres, og det element, der skal søges, er funderet. Hvis vi taler om effektiviteten, er effektiviteten det antal gange, programmet skal køre for at finde antallet. Hvis vi finder det nummer, vi leder efter i den første position, skal der kun foretages en sammenligning, og tingene sorteres, men hvis ikke, skal sammenligninger foretages igen og igen, og hukommelsen spildes. I gennemsnit vil antallet af sammenligninger være (n + 1/2). Og den værste sag effektivitet af denne teknik er O (n) står for rækkefølgen af udførelse.

Sammenlignet med den lineære søgning er binær søgning meget effektiv. I denne metode er arrayet opdelt i to dele, og på denne måde er antallet af sammenligninger meget mindre sammenlignet med binær søgning. Tiden er også mindre i binær søgning sammenlignet med lineær søgning. Binært søgning fungerer på den måde, som det midterste element i arrayet findes, og derefter sammenlignes det midterste element med en del af array. Der kan være tre muligheder, der er midterste antal, kan være det nummer, vi har brug for at finde, eller det antal, der er mindre end det midterste tal eller det antal, der er større end midten af det midterste antal. Antallet af sammenligninger er højst log (N + 1). Binær søgning sammenlignet med lineær søgning er en effektiv algoritme sammenlignet med lineær søgning, men arrayet skal sorteres, inden den binære søgning udføres.

Indhold: Forskel mellem lineær søgning og binær søgning

Sammenligningstabel
Binær søgning
Vigtige forskelle
Konklusion
Forklarende video

Sammenligningstabel

Basis	Lineær søgning	Binær søgning
Betyder	Lineær søgning hvert element kontrolleres og sammenlignes og sorteres derefter	Binær søgning en liste, der skal sorteres, er opdelt i to dele og derefter sorteret.
Tidskompleksitet	Tidskompleksiteten for den lineære søgning er O (N).	Tidskompleksiteten for den binære søgning er O (log ₂ N)
Type algoritme	Lineær søgning er iterativ.	Binær søgning er Opdel og erobre.
Line of code	I en lineær søgning skal vi skrive mere kode.	I en binær søgning er vi nødt til at skrive mindre kode.

Lineær søgning

Lineær søgning er en meget kompleks algoritme, hvis du vil søge i et tal på en liste, sammenligne og itereere nogle gange antallet af værdier på listen. Ét efter et hvert element på listen hentes og sammenlignes med det tilstødende element. Alle elementer åbnes og kontrolleres, og så findes det rigtige element. Der kan være det værste tilfælde, hvis det sidste nummer på listen er det nummer, der skal søges. Lineær søgning er den metode, hvorpå arrayet gennemskæres, og det element, der skal søges, er funderet. Hvis vi taler om effektiviteten, er effektiviteten det antal gange, programmet skal køre for at finde antallet. Hvis vi finder det nummer, vi leder efter i den første position, skal der kun foretages en sammenligning, og tingene sorteres, men hvis ikke, skal sammenligninger foretages igen og igen, og hukommelsen spildes. I gennemsnit vil antallet af sammenligninger være (n + 1/2). Og i værste fald effektiviteten af denne teknik er O (n) står for rækkefølgen af udførelse.

Binær søgning

Sammenlignet med lineær søgning er binær søgning meget effektiv. I denne metode er arrayet delt i to dele, og på denne måde er antallet af sammenligninger meget mindre sammenlignet med binær søgning. Tiden er også mindre i binær søgning sammenlignet med lineær søgning. Binært søgning fungerer på den måde, som det midterste element i arrayet findes, og derefter sammenlignes det midterste element med en del af arrayet.

Der kan være tre muligheder, der er midterste antal, kan være det nummer, vi har brug for at finde, eller det antal, der er mindre end det midterste tal eller det antal, der er større end midten af det midterste antal. Antallet af sammenligninger er højst log (N + 1). Binær søgning sammenlignet med lineær søgning er en effektiv algoritme sammenlignet med lineær søgning, men arrayet skal sorteres, inden den binære søgning udføres.

Vigtige forskelle

Lineær søgning hvert element kontrolleres og sammenlignes og sorteres derefter, mens Binær søgning en liste, der skal sorteres, er opdelt i to dele og derefter sorteret.
Tidskompleksiteten for lineær søgning er 0 (N), mens tidskompleksiteten for binær søgning er O (log₂N).
Lineær søgning er iterativ, hvorimod binær søgning er skille og erobre.
Ved lineær søgning skal vi skrive mere kode, mens vi i binær søgning skal skrive mindre kode.