Objašnjeni algoritmi linearnog i binarnog pretraživanja

Sposobnost pretraživanja nekih podataka važan je aspekt računalne znanosti. Algoritmi pretraživanja koriste se za traženje određene stavke u skupu podataka.

Algoritmi vraćaju logički rezultat (istinit ili netočan) u upit za pretraživanje. Također se mogu izmijeniti kako bi se dobio relativni položaj pronađene vrijednosti.

U ovom članku algoritmi će se koncentrirati na utvrđivanje postoji li vrijednost.

Algoritmi linearnog pretraživanja

Linearno pretraživanje poznato je i kao sekvencijalno pretraživanje. U ovoj vrsti pretraživanja, svaka vrijednost na popisu posjećuje se jedna po jedna na uredan način, dok se provjerava postoji li željena vrijednost.

Algoritam provjerava vrijednost po vrijednost dok ne pronađe vrijednost koju tražite ili nema dovoljno vrijednosti za pretraživanje. Kad ponestane vrijednosti za pretraživanje, to znači da vaš upit za pretraživanje ne postoji na popisu.

Algoritam sekvencijalnog pretraživanja uzima kao parametre popis vrijednosti i željenu stavku na popisu. Povratni rezultat se inicijalizira kao

Netočno i promijenit će se u Pravi kada se pronađe željena vrijednost.

Kao primjer pogledajte implementaciju Pythona u nastavku:

def linearSearch (moj popis, stavka):

pronađeno = Netačno

indeks = 0

dok indeks

ako je mylist [index] == stavka:

pronađeno = Istina

drugo:

indeks = indeks+1

povratak pronađen

Algoritamska analiza

Najbolji scenarij događa se kada je željena stavka prva na popisu. Najgori slučaj događa se kada je željena stavka zadnja na popisu (n -ta stavka). Stoga je vremenska složenost linearnog pretraživanja O (n).

Prosječni scenarij slučaja u gornjem algoritmu je n/2.

Povezano: Što je oznaka Big-O?

Izmijenjeno linearno pretraživanje

Važno je znati da korišteni algoritam pretpostavlja da mu se daje nasumičan popis stavki. Odnosno, stavke popisa nisu u određenom redoslijedu.

Pretpostavimo da su stavke bile u određenom redoslijedu, recimo od najmanjeg do najvećeg. Moglo bi se postići neka prednost u računanju.

Uzmite primjer traženja 19 na danom popisu: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Nakon što dosegne 23, postat će jasno da stavka koju tražite ne postoji na popisu. Stoga više ne bi bilo važno nastaviti pretraživati ​​ostatak stavki popisa.

Binarni algoritmi pretraživanja

Vidjeli ste kako uređen popis može smanjiti potrebno izračunavanje. Binarni algoritam pretraživanja još više iskorištava ovu učinkovitost nego što ima uređen popis.

Algoritam započinje uzimanjem srednje vrijednosti uređenog popisa i provjerom je li to željena vrijednost. Ako nije, tada se provjerava je li manja ili veća od željene vrijednosti.

Ako je manji, nema potrebe provjeravati donju polovicu popisa. Inače, ako je veći, prelazi na gornju polovicu popisa.

Povezano: Što je rekurzija i kako je koristiti?

Bez obzira na to koji se podskup (lijevi ili desni) odabere, srednja vrijednost će se ponovno odrediti. Vrijednost se ponovno provjerava je li potrebna vrijednost. Ako nije, provjerava se je li manja ili veća od tražene vrijednosti.

Ovaj se postupak ponavlja sve dok se ne pronađe vrijednost ako postoji.

Python implementacija u nastavku služi za binarni algoritam pretraživanja.

def binarySearch (mylist, item):

niska = 0

visoka = len (moj popis) - 1

pronađeno = Netačno

dok je nisko <= visoko i nije pronađeno:

sredina = (niska + visoka) // 2

if mylist [mid] == item:

pronađeno = Istina

elif stavka

visoka = sredina - 1

drugo:

niska = srednja + 1

povratak pronađen

Algoritamska analiza

Najbolji scenarij događa se kada se utvrdi da je željena stavka srednja stavka. Najgori mogući scenarij ipak nije tako jednostavan. Slijedite donju analizu:

Nakon prve usporedbe ostat će n/2 stavki. Nakon druge, ostavit će se n/4 stavke. Nakon treće, n/8.

Uočite da se broj stavki nastavlja prepolovljavati sve dok ne dosegnu n/2i gdje je i broj usporedbi. Nakon cijepanja, završavamo sa samo 1 stavkom.

Iz čega slijedi:

n/2i = 1

Stoga je binarno pretraživanje O (log n).

Prelazimo na sortiranje

U binarnom pretraživanju razmotrili smo slučaj gdje je zadani niz već naručen. No pretpostavimo da ste imali neuređen skup podataka i da ste htjeli izvršiti binarno pretraživanje na njemu. Što bi ti napravio?

Odgovor je jednostavan: sredite to. U računalnoj znanosti postoji niz tehnika sortiranja koje su dobro istražene. Jedna od ovih tehnika koju možete početi proučavati je algoritam sortiranja odabira, dok imamo dosta vodiča vezanih i za druga područja.

Kako koristiti sortiranje odabira

Početnički je odabir pomalo nezgodno za razumjeti, ali nije previše izazovan kad se shvati.

Pročitajte Dalje

O autoru