Lineære og binære søgningsalgoritmer forklaret

Evnen til at søge efter nogle data er et vigtigt aspekt af datalogi. Søgealgoritmer bruges til at lede efter et bestemt element i et datasæt.

Algoritmer returnerer et boolsk resultat (sandt eller forkert) til en søgeforespørgsel. De kan også ændres for at give den fundne værdi den relative position.

For denne artikel vil algoritmerne koncentrere sig om at bestemme, om der findes en værdi.

Lineære søgealgoritmer

Lineær søgning er også kendt som sekventiel søgning. I denne type søgning besøges hver værdi i en liste en efter en på en ordnet måde, mens der kontrolleres, om den ønskede værdi findes.

Algoritmen kontrollerer værdi efter værdi, indtil den finder den værdi, du leder efter, eller den løber tør for værdier til søgning. Når det løber tør for værdier til søgning, betyder det, at din søgeforespørgsel ikke findes på listen.

En sekventiel søgealgoritme optager en liste med værdier og det ønskede element på listen som sine parametre. Returneringsresultatet initialiseres som Falsk og vil ændre til Rigtigt når den ønskede værdi er fundet.

Se Python -implementeringen herunder som et eksempel:

def linearSearch (mylist, item):

fundet = Falsk

indeks = 0

mens indeks

hvis mylist [index] == element:

fundet = sandt

andet:

indeks = indeks+1

retur fundet

Algoritme analyse

Det bedste tilfælde opstår, når det ønskede element er det første på listen. Det værste tilfælde opstår, når det ønskede element er det sidste på listen (det niende element). Derfor er tidskompleksiteten for lineær søgning O (n).

Det gennemsnitlige case scenario i ovenstående algoritme er n/2.

Relaterede: Hvad er Big-O Notation?

Ændret lineær søgning

Det er vigtigt at vide, at den anvendte algoritme forudsætter, at der leveres en tilfældig liste over emner til den. Det vil sige, at listeelementerne ikke er i nogen særlig rækkefølge.

Antag, at varerne var i en bestemt rækkefølge, siger fra mindste til største. Det ville være muligt at opnå en vis fordel inden for beregning.

Tag et eksempel på at lede efter 19 på den givne liste: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Efter at have nået 23, ville det blive klart, at det element, der søges efter, ikke findes på listen. Derfor ville det ikke længere være vigtigt at fortsætte med at søge i resten af ​​listeelementerne.

Binære søge algoritmer

Du har set, hvordan en ordnet liste kan reducere den nødvendige beregning. Binær søgealgoritme drager endnu større fordel af denne effektivitet, som en ordnet liste introducerer.

Algoritmen begynder med at tage en mellemværdi af en ordnet liste og kontrollere, om det er den ønskede værdi. Hvis det ikke er det, kontrolleres værdien, om den er mindre eller større end den ønskede værdi.

Hvis det er mindre, er det ikke nødvendigt at kontrollere den nederste halvdel af listen. Hvis den ellers er større, går den videre til den øverste halvdel af listen.

Relaterede: Hvad er rekursion, og hvordan bruger du det?

Uanset hvilken underliste (venstre eller højre) der vælges, bestemmes midterværdien igen. Værdien kontrolleres igen, hvis det er den nødvendige værdi. Hvis det ikke er det, kontrolleres det, om det er mindre eller større end den ønskede værdi.

Denne proces gentages, indtil der findes en værdi, hvis den er der.

Python -implementeringen herunder er til den binære søge -algoritme.

def binarySearch (mylist, item):

lav = 0

høj = len (mylist) - 1

fundet = Falsk

mens lav <= høj og ikke fundet:

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

hvis mylist [mid] == element:

fundet = sandt

elif element

høj = midten - 1

andet:

lav = mid + 1

retur fundet

Algoritme analyse

Det bedste tilfælde opstår, når det viste sig, at det ønskede element er det midterste element. Det værste tilfælde er dog ikke lige så ligetil. Følg analysen herunder:

Efter den første sammenligning vil n/2 varer blive tilbage. Efter den anden vil n/4 varer blive tilbage. Efter den tredje, n/8.

Bemærk, at antallet af varer bliver ved med at halvere, indtil de når n/2i, hvor i er antallet af sammenligninger. Efter al splittelsen ender vi med kun 1 vare.

Dette indebærer:

n/2i = 1

Derfor er binær søgning O (log n).

Gå videre til sortering

I binær søgning overvejede vi et tilfælde, hvor det givne array allerede var bestilt. Men antag, at du havde et uordnet datasæt, og du ville udføre binær søgning på det. Hvad ville du gøre?

Svaret er enkelt: sorter det. Der er en række sorteringsteknikker inden for datalogi, der er blevet undersøgt godt. En af disse teknikker, du kan begynde at studere, er selektionssorteringsalgoritmen, mens vi også har masser af guider relateret til andre områder.

Sådan bruges markeringssortering

Udvælgelsessort er lidt vanskelig at forstå for begyndere, men det er ikke for udfordrende, når du først får sving i tingene.

Læs Næste

Om forfatteren