Preporučeno, 2019

Izbor Urednika

Razlika između linearnog pretraživanja i binarnog pretraživanja

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

Glavna razlika između linearnog pretraživanja i binarnog pretraživanja je da binarno pretraživanje traje manje vremena za pretraživanje elementa iz razvrstane liste elemenata. Stoga se zaključuje da je učinkovitost binarne metode pretraživanja veća od linearnog pretraživanja.

Druga razlika između njih je da postoji preduvjet za binarno pretraživanje, tj. Elementi moraju biti razvrstani, dok u linearnom pretraživanju nema takvog preduvjeta. Iako obje metode pretraživanja koriste različite tehnike koje su opisane u nastavku.

Tablica usporedbe

Osnova za usporedbuLinearno pretraživanjeBinarno pretraživanje
Složenost vremenaNA)O (log 2 N)
Najbolje vrijemePrvi element O (1)Središnji element O (1)
Preduvjet za nizNije potrebnoNiz mora biti poredan
Najgori slučaj za N broj elemenataNužne su usporedbeMože zaključiti samo nakon usporedbe log 2 N
Može se implementirati naNiz i povezani popisNe može se izravno implementirati na povezani popis
Umetnite radJednostavno se umeće na kraj popisaZahtijevajte obradu da biste umetnuli na svoje pravo mjesto za održavanje sortirane liste.
Tip algoritmaIterativna u prirodiPodijelite i osvojite u prirodi
KorisnostJednostavan je za korištenje i nema potrebe za bilo kojim naručenim elementima.U svakom slučaju, lukav algoritam i elementi trebaju biti organizirani po redu.
Linije kodaManjeViše

Definicija linearnog pretraživanja

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

Stoga se linearno pretraživanje može definirati kao tehnika koja slijedno slijedi niz kako bi locirala zadanu stavku. Dolje prikazani program ilustrira pretraživanje elementa polja pomoću pretraživanja.

Učinkovitost linearnog pretraživanja

Utrošak vremena ili broj usporedbi u pretraživanju zapisa u tablici pretraživanja određuje učinkovitost tehnike. Ako je željeni zapis prisutan u prvom položaju tablice pretraživanja, tada se radi samo jedna usporedba. Kada je željeni zapis posljednji, potrebno je napraviti n usporedbi. Ako je zapis prikazan negdje u tablici pretraživanja, u prosjeku, broj usporedbi će biti (n + 1/2). Najgori slučaj učinkovitosti ove tehnike je O (n) za redoslijed izvršenja.

C Program za pretraživanje elementa s linearnom tehnikom pretraživanja.

 #include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("Unesite broj elementa:"); scanf ("% d", & n); printf ("Unesite brojeve: n"); za (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Unesite broj koji se traži:"); scanf ("% d", & item); za (i = 0; i = 0) {printf ("n% d se nalazi na položaju% d:", item, loc + 1); } else {printf ("ne postoji stavka"); } getch (); } 

Definicija binarnog pretraživanja

Binarno pretraživanje je iznimno učinkovit algoritam. Ova tehnika pretraživanja troši manje vremena u pretraživanju zadane stavke u minimalnim mogućim usporedbama. Da biste izvršili binarno pretraživanje, prvo moramo razvrstati elemente niza.

Logika ove tehnike data je u nastavku:

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

Mogu se pojaviti tri slučaja:

  1. Ako je element traženi element, pretraživanje je uspješno.
  2. Kada 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.

Ponovite iste korake dok se ne pronađe neki element ili se isprazni u području pretraživanja. U ovom algoritmu, svako područje pretraživanja vremena se 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 polje se mora sortirati prije binarnog pretraživanja.

C Program za pronalaženje elementa s binarnom tehnikom pretraživanja.

 #include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Unesite broj elementa"); scanf ( "% d", i n); printf ("Unesite% d brojeva n", n); za (i = 0; i <n; i ++) scanf ("% d", i niz [i]); printf ("Unesite broj koji se traži"); scanf ("% d", & pretraživanje); beg = 0; kraj = n - 1; sredina = (mol + kraj) / 2; while (beg <= end) {if (niz [srednji] kraj) printf ("Pretraživanje je neuspješno!% d nije na popisu. \ t getch (); } 

Ključne razlike između linearnog pretraživanja i binarnog pretraživanja

  1. Linearno pretraživanje je po prirodi iterativno 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 binarno pretraživanje ima O (log 2 N).
  3. Najbolje vrijeme u linearnom pretraživanju je za prvi element, tj. O (1). Nasuprot 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. Nasuprot tome, to je log 2 N broj usporedbe za binarno pretraživanje.
  5. Linearno pretraživanje može biti implementirano u nizu, kao iu povezanom popisu, dok binarno pretraživanje ne može biti implementirano izravno na povezanom popisu.
  6. Kao što znamo Binarno pretraživanje zahtijeva sortirani niz koji je razlog. Za obradu je potrebno umetnuti na svoje pravo mjesto za održavanje sortirane liste. Nasuprot tome, linearno pretraživanje ne zahtijeva sortirane elemente, tako da se elementi lako ubacuju na kraj popisa.
  7. Linearno pretraživanje je jednostavno za korištenje i nema potrebe za bilo kojim naručenim elementima. S druge strane, algoritam binarnog pretraživanja je ipak lukav, a elementi su nužno poredani redom.

Zaključak

Ovisno o primjeni, mogu biti korisni i linearni i binarni algoritmi pretraživanja. Kada je niz podataka struktura i elementi su raspoređeni u sortiranom redoslijedu, onda binarno pretraživanje je poželjno za brzo pretraživanje. Ako je povezani popis podatkovna struktura bez obzira na to kako su elementi raspoređeni, linearno pretraživanje se usvaja zbog nedostupnosti izravne implementacije binarnog algoritma pretraživanja.

Tipični binarni algoritam pretraživanja ne može se primijeniti na povezani popis jer je povezan popis dinamičan po prirodi i nije poznato gdje je srednji element zapravo dodijeljen. Dakle, postoji zahtjev za dizajniranjem varijacije binarnog algoritma pretraživanja koji može raditi i na povezanom popisu, jer je binarno pretraživanje brže u izvršenju od linearnog pretraživanja.

Top