Lineære og binære søkealgoritmer forklart

Evnen til å søke etter noen data er et viktig aspekt ved datavitenskap. Søkealgoritmer brukes til å lete etter et bestemt element i et datasett.

Algoritmer returnerer et boolsk resultat (sant eller usant) til et søk. De kan også modifiseres for å gi den relative posisjonen til funnet verdi.

For denne artikkelen vil algoritmene konsentrere seg om å avgjøre om det finnes en verdi.

Lineære søkealgoritmer

Lineært søk er også kjent som sekvensielt søk. I denne typen søk blir hver verdi i en liste besøkt en etter en på en ryddig måte mens du sjekker om ønsket verdi eksisterer.

Algoritmen sjekker verdi etter verdi til den finner verdien du leter etter eller går tom for verdier for å søke. Når det går tom for verdier for å søke, betyr det at søket ditt ikke finnes i listen.

En sekvensiell søkealgoritme tar inn en liste med verdier og ønsket element i listen som sine parametere. Returresultatet initialiseres som Falsk og vil endre seg til ekte når ønsket verdi er funnet.

Se Python -implementeringen nedenfor som et eksempel:

def linearSearch (mylist, item):

funnet = Falske

indeks = 0

mens indeks

hvis mylist [index] == element:

funnet = Sant

ellers:

indeks = indeks+1

retur funnet

Algoritme analyse

Det beste tilfellet skjer når det ønskede elementet er det første på listen. Det verste tilfellet oppstår når ønsket element er det siste på listen (det niende elementet). Derfor er tidskompleksiteten for lineært søk O (n).

Gjennomsnittlig case -scenario i algoritmen ovenfor er n/2.

I slekt: Hva er Big-O Notation?

Endret lineært søk

Det er viktig å vite at algoritmen som brukes, forutsetter at den er gitt en tilfeldig liste over elementer. Det vil si at listeelementene ikke er i noen spesiell rekkefølge.

Anta at varene var i en bestemt rekkefølge, si fra minste til største. Det ville være mulig å oppnå en viss fordel i beregning.

Ta et eksempel på å lete etter 19 i den gitte listen: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Etter å ha nådd 23, ville det bli klart at varen du leter etter ikke finnes i listen. Derfor ville det ikke lenger være viktig å fortsette å søke i resten av listeelementene.

Binære søkealgoritmer

Du har sett hvordan en ordnet liste kan redusere beregningen som trengs. Binær søkealgoritme drar enda mer fordel av denne effektiviteten som det å ha en ordnet liste introduserer.

Algoritmen begynner med å ta en mellomverdi av en ordnet liste og kontrollere om det er ønsket verdi. Hvis det ikke er det, kontrolleres verdien om den er mindre eller større enn ønsket verdi.

Hvis det er mindre, er det ikke nødvendig å sjekke den nedre halvdelen av listen. Ellers, hvis den er større, går den videre til den øvre halvdelen av listen.

I slekt: Hva er rekursjon og hvordan bruker du det?

Uavhengig av hvilken sublist (venstre eller høyre) som velges, vil mellomverdien igjen bli bestemt. Verdien kontrolleres igjen hvis det er den nødvendige verdien. Hvis det ikke er det, kontrolleres det om det er mindre eller større enn den forespurte verdien.

Denne prosessen gjentas til en verdi er funnet hvis den er der.

Python -implementeringen nedenfor er for den binære søkealgoritmen.

def binarySearch (mylist, item):

lav = 0

høy = len (mylist) - 1

funnet = Falske

mens lav <= høy og ikke funnet:

mid = (lav + høy) // 2

hvis mylist [mid] == element:

funnet = Sant

elif element

høy = midten - 1

ellers:

lav = midten + 1

retur funnet

Algoritme analyse

Det beste tilfellet skjer når det ønskede elementet er funnet som det midterste elementet. Det verste tilfellet er imidlertid ikke like greit. Følg analysen nedenfor:

Etter den første sammenligningen vil n/2 varer bli igjen. Etter den andre vil n/4 elementer bli igjen. Etter den tredje, n/8.

Legg merke til at antallet varer fortsetter å halvere til de når n/2i hvor i er antallet sammenligninger. Etter all splittelsen ender vi opp med bare 1 vare.

Dette innebærer:

n/2i = 1

Derfor er binært søk O (log n).

Går videre til sortering

I binært søk vurderte vi et tilfelle der den gitte matrisen allerede var bestilt. Men anta at du hadde et uordnet datasett, og at du ønsket å utføre binært søk på det. Hva ville du gjort?

Svaret er enkelt: sorter det. Det er en rekke sorteringsteknikker innen informatikk som har blitt godt undersøkt. En av disse teknikkene du kan begynne å studere er utvalgssorteringsalgoritmen, mens vi har mange guider knyttet til andre områder også.

Slik bruker du utvalgssortering

Utvalgssortering er litt vanskelig å forstå for nybegynnere, men det er ikke så utfordrende når du først får sving i tingene.

Les neste

Om forfatteren