Sadržaj

• Usporedni grafikon
• Definicija linearnog pretraživanja
• Definicija binarne pretrage
• Zaključak

Linearno pretraživanje i binarno pretraživanje dvije su metode koje se koriste u nizovima pretraživanje elementi. Pretraživanje je postupak pronalaska elementa unutar popisa elemenata pohranjenih bilo kojim redoslijedom ili nasumično.

Glavna razlika između linearnog pretraživanja i binarnog pretraživanja je ta što binarnom pretraživanju treba manje vremena za pretraživanje elemenata s poredanog popisa elemenata. Stoga je zaključeno da je učinkovitost metode binarnog pretraživanja veća od linearnog pretraživanja.

Još jedna razlika između njih je da postoji preduvjet za binarno pretraživanje, tj. Da elementi moraju biti sortirati dok u linearnom pretraživanju ne postoji takav preduvjet. Iako obje metode pretraživanja koriste različite tehnike koje su navedene u nastavku.

1. Usporedni grafikon
2. definicija
3. Ključne razlike
4. Zaključak

Usporedni grafikon

Osnove za usporedbu	Linearna pretraga	Binarna pretraga
Vremenska složenost	NA)	O (log 2 N)
Najbolje vrijeme za slučaj	Prvi element O (1)	Središnji element O (1)
Preduvjet za niz	Nije potrebno	Niz mora biti razvrstan
Najgori slučaj za N broj elemenata	Nije potrebna usporedba	Može zaključiti nakon samo zapisa2N usporedbe
Može se implementirati na	Niz i povezani popis	Nije moguće izravno implementirati na povezanom popisu
Umetnite radnju	Jednostavno se ubacuje na kraju popisa	Za održavanje sortiranog popisa zatražite obradu da biste je umetnuli na svom mjestu.
Vrsta algoritma	Iterativne prirode	Podijelite i osvajajte u prirodi
Korisnost	Jednostavan je za uporabu i nema potrebe za naručenim elementima.	U svakom slučaju, složeni algoritam i elementi trebaju se organizirati redoslijedom.
Linije koda	Manje	Više

Definicija linearnog pretraživanja

Pri linearnom pretraživanju svaki se element niza dohvaća jedan po jedan u logičkom redoslijedu i provjerava je li željeni element ili ne. Pretraživanje neće biti uspješno ako se pristupi svim elementima, a željeni element ne bude pronađen. U najgorem slučaju, broj prosječnog slučaja možda ćemo morati skenirati polovinu veličine matrice (n / 2).

Stoga se linearno pretraživanje može definirati kao tehnika koja sekvencijalno obilazi niz kako bi pronašla zadani element. Program dan u nastavku ilustrira pretraživanje elementa niza pomoću pretraživanja.

efikasnost linearnog pretraživanja

Potrošnja vremena ili broj usporedba u pretraživanju zapisa u pretraživačkoj tablici određuje učinkovitost tehnike. Ako se željeni zapis nalazi na prvom mjestu tablice pretraživanja, tada se vrši samo jedna usporedba. Kad je željeni zapis posljednji, tada se mora napraviti n usporedba. Ako se zapis treba negdje naći u tablici pretraživanja, u prosjeku će biti broj usporedbi (n + 1/2). Najgora učinkovitost ove tehnike je O (n) za redoslijed izvođenja.

Program C za pretraživanje elementa pomoću tehnike linearnog pretraživanja.

#include #include void main () {int a, n, i, stavka, loc = -1; clrscr (); f (" nUnesite broj elementa:"); scanf ("% d", & n); f ("Unesite brojeve: n"); za (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nUnesite broj koji se traži:"); scanf ("% d", & stavka); za (i = 0; i <= n-1; i ++) {if (stavka == a) {loc = i; pauza; }} if (loc> = 0) {f (" n% d se nađe u položaju% d:", stavka, loc + 1); } else {f (" n Stavka ne postoji"); } getch (); }

Definicija binarne pretrage

Binarna pretraga izuzetno je učinkovit algoritam. Ova tehnika pretraživanja zahtijeva manje vremena za pretraživanje datog predmeta u minimalnim mogućim usporedbama. Da bismo izvršili binarno pretraživanje, prvo moramo razvrstati elemente niza.

Logika koja stoji iza ove tehnike dana je u nastavku:

• Prvo pronađite srednji element matrice.
• Srednji element matrice uspoređuje se s elementom koji se traži.

Mogu se pojaviti tri slučaja:

1. Ako je element potreban element, tada je pretraživanje uspješno.
2. Kad je element manji od željene stavke, pretražite samo prvu polovicu polja.
3. Ako je veći od željenog elementa, pretražite u drugoj polovici polja.

Ponavljajte iste korake dok se element ne nađe ili iscrpi u području pretraživanja. U ovom se algoritmu svako vrijeme pretraživanja smanjuje. Stoga je broj usporedbi najviše log (N + 1). Kao rezultat toga, to je učinkovit algoritam u usporedbi s linearnim pretraživanjem, ali niz se mora sortirati prije nego što se izvrši binarno pretraživanje.

Program C pronaći element pomoću binarne tehnike pretraživanja.

#include void main () {int i, beg, kraj, sredina, n, traži, niz; f ("Unesite broj elementa n"); scanf ( "% d", i n); f ("Unesite% d brojeve n", n); za (i = 0; i <n; i ++) scanf ("% d", & niz); f ("Unesite broj za pretraživanje n"); scanf ("% d", & traži); beg = 0; kraj = n - 1; sredina = (prosjak + kraj) / 2; dok (beg <= kraj) {if (niz <search) beg = sredina + 1; else if (array == search) {f ("Pretraživanje je uspješno. n% d pronađeno na lokaciji% d. n", traži, sredina + 1); pauza; } else end = sredina - 1; sredina = (prosjak + kraj) / 2; } if (beg> end) f ("Pretraga je neuspješna!% d nije prisutna na popisu. n", pretraživanje); getch (); }

1. Linearna pretraga je iterativne prirode i koristi sekvencijalni pristup. S druge strane, binarno pretraživanje provodi pristup podijeli i osvoji.
2. Vremenska složenost linearnog pretraživanja je O (N), dok binarna pretraga ima O (zapisnik)₂N).
3. Najbolje vrijeme slučaja u linearnom pretraživanju je za prvi element, tj. O (1). Suprotno tome, u binarnom pretraživanju to je za srednji element, tj. O (1).
4. U linearnom pretraživanju najgori slučaj za pretraživanje elementa je N broj usporedbe. Suprotno tome, to je zapisnik₂N broj usporedbe za binarno pretraživanje.
5. Linearno pretraživanje može se provesti u nizu i na povezanom popisu, dok se binarno pretraživanje ne može provoditi izravno na povezanom popisu.
6. Kao što znamo Binarna pretraga zahtijeva razvrstani niz koji je razlog što je potrebna obrada radi umetanja na odgovarajuće mjesto radi održavanja poredanog popisa. Suprotno tome, linearno pretraživanje ne zahtijeva razvrstane elemente, pa se elementi lako ubacuju na kraj popisa.
7. Linearno pretraživanje lako je koristiti i nema potrebe za bilo kojim naručenim elementima. S druge strane, algoritam binarnog pretraživanja ipak je lukav i elementi su nužno raspoređeni po redu.

Zaključak

I linearni i binarni algoritmi pretraživanja mogu biti korisni ovisno o aplikaciji. Kad je niz podataka struktura podataka i elementi su raspoređeni u razvrstanom redoslijedu, tada se preferira binarno pretraživanje brztraži. Ako je povezani popis struktura podataka bez obzira na to kako su elementi uređeni, linearno pretraživanje usvaja se zbog nedostupnosti izravne implementacije algoritma binarnog pretraživanja.

Tipični algoritam binarnog pretraživanja ne može se koristiti na povezanom popisu, jer je povezani popis dinamične prirode i nije poznato gdje je srednji element zapravo dodijeljen. Stoga postoji potreba za dizajniranjem varijacija algoritma binarnog pretraživanja koji može raditi i na povezanom popisu jer je binarno pretraživanje brže izvršeno od linearnog pretraživanja.