Suurin ero lineaarisen haun ja binäärisen haun välillä on, että binäärinen haku vie vähemmän aikaa etsimään elementtiä lajiteltujen elementtien luettelosta. Niinpä päätellään, että binäärisen hakumenetelmän tehokkuus on suurempi kuin lineaarinen haku.
Toinen ero näiden kahden välillä on, että binäärisen haun edellytys on, eli elementit on lajiteltava, kun lineaarisessa haussa ei ole tällaista edellytystä. Vaikka molemmat hakumenetelmät käyttävät erilaisia tekniikoita, joita käsitellään alla.
Vertailukaavio
| Vertailun perusteet | Lineaarinen haku | Binaarihaku |
|---|---|---|
| Ajan monimutkaisuus | PÄÄLLÄ) | O (log 2 N) |
| Paras tapaustapa | Ensimmäinen elementti O (1) | Center Element O (1) |
| Edellytykset ryhmälle | Ei tarvita | Arrayn on oltava lajitellussa järjestyksessä |
| Pahimmassa tapauksessa N-elementtien lukumäärä | N vertailuja tarvitaan | Voi päätellä vain log 2 N vertailujen jälkeen |
| Voidaan toteuttaa | Array- ja Linked-luettelo | Ei voida suoraan toteuttaa linkitetyssä luettelossa |
| Lisää toiminto | Lisää helposti luettelon loppuun | Vaadi käsittelyä, jos haluat lisätä sen oikeaan paikkaan lajitellun luettelon ylläpitämiseksi. |
| Algoritmityyppi | Iteratiivinen luonnossa | Jaa ja valloita luonnossa |
| Hyödyllisyys | Helppokäyttöinen ja ei tarvita tilattuja elementtejä. | Joka tapauksessa hankala algoritmi ja elementit olisi järjestettävä järjestyksessä. |
| Koodilinjat | Vähemmän | Lisää |
Lineaarisen haun määritelmä
Lineaarisessa haussa jokainen taulukon elementti haetaan yksitellen loogisessa järjestyksessä ja tarkistetaan, onko se haluttu elementti vai ei. Haku ei onnistu, jos kaikki elementit ovat käytettävissä, ja haluttua elementtiä ei löydy. Pahimmassa tapauksessa keskimääräisen tapauksen määrä, johon meidän täytyy joutua skannaamaan puolet taulukon koosta (n / 2).
Siksi lineaarinen haku voidaan määritellä tekniikaksi, joka kulkee taulukon peräkkäin etsimään tietyn kohteen. Alla oleva ohjelma havainnollistaa ryhmän elementin etsintää haun avulla.
Lineaarisen haun tehokkuus
Aikakulutus tai tietueiden etsinnässä hakutaulukossa tehtyjen vertailujen määrä määrittää tekniikan tehokkuuden. Jos haluttu tietue löytyy hakutaulukon ensimmäisestä sijainnista, tehdään vain yksi vertailu. Kun haluttu ennätys on viimeinen, on tehtävä n vertailu. Jos ennätys on tarkoitus esittää jossakin hakutaulukossa, vertailujen määrä on (n + 1/2). Tämän tekniikan pahin tapaustehokkuus on O (n), joka tarkoittaa toteutuksen järjestystä.
C Ohjelma etsiä elementtiä, jolla on lineaarinen hakutekniikka.
#include #include void main () {int a [100], n, i, kohde, loc = -1; clrscr (); printf ("Kirjoita elementin numero:"); scanf ("% d", & n); printf ("Syötä numerot: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Kirjoita haettava numero:"); scanf ("% d", & kohde); (i = 0; i = 0) {printf ("n% d löytyy asemasta% d:", kohde, loc + 1); } else {printf ("Tuotetta ei ole olemassa"); } getch (); } Binäärisen haun määritelmä
Binäärinen haku on erittäin tehokas algoritmi. Tämä hakutekniikka kuluttaa vähemmän aikaa tietyn kohteen etsinnässä mahdollisimman pienissä vertailuissa. Binäärisen haun suorittamiseksi meidän on ensin lajiteltava taulukkoelementit.
Tämän tekniikan logiikka on esitetty alla:
- Etsi ensin taulukon keskiosa.
- Ryhmän keskiosaa verrataan haettavaan elementtiin.
Saattaa olla kolme tapausta:
- Jos elementti on vaadittu elementti, haku on onnistunut.
- Kun elementti on pienempi kuin haluttu kohde, etsi vain taulukon ensimmäinen puoli.
- Jos se on suurempi kuin haluttu elementti, etsi taulukon toinen puoli.
Toista samat vaiheet, kunnes etsintäalueella löytyy elementti tai pakokaasu. Tässä algoritmissa aina kun hakualue vähenee. Siksi vertailujen lukumäärä on korkeintaan log (N + 1). Tämän seurauksena se on tehokas algoritmi verrattuna lineaariseen hakuun, mutta matriisi on lajiteltava ennen binäärisen haun tekemistä.
C Ohjelma löytää elementti, jossa on binäärinen hakutekniikka.
#include void main () {int i, kerjääminen, loppu, keski, n, haku, taulukko [100]; printf ("Anna elementin numero"); scanf ( "% d", ja n); printf ("Syötä% d numerot n", n); (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Anna haettava numero"); scanf ("% d" ja haku); kerro = 0; end = n - 1; keskimmäinen = (beg + end) / 2; kun (kerro <= loppu) {if (array [middle] end) printf ("Haku ei onnistu!% d ei ole luettelossa." getch (); } Lineaarisen haun ja binäärisen haun tärkeimmät erot
- Lineaarinen haku on luonteeltaan iteratiivinen ja käyttää peräkkäistä lähestymistapaa. Toisaalta binäärihaku toteuttaa jakamista ja valloittamista.
- Lineaarisen haun aikakompleksisuus on O (N), kun taas binäärisen haun O on (log 2 N).
- Paras tapausaika lineaarisessa haussa on ensimmäiselle elementille eli O (1). Binäärisen haun kohdalla se on keskielementille eli O (1).
- Lineaarisessa haussa pahin tapa etsiä elementtiä on N: n vertailuarvo. Sitä vastoin binäärisen haun vertailuarvo on log 2 N.
- Lineaarinen haku voidaan toteuttaa ryhmässä sekä linkitetyssä luettelossa, kun taas binääristä hakua ei voida toteuttaa suoraan linkitetyssä luettelossa.
- Kuten tiedämme, binaarihaku vaatii lajitellun taulukon, joka on syy. Se vaatii käsittelyä, jotta se voidaan lisätä oikeaan paikkaan lajitellun luettelon ylläpitämiseksi. Päinvastoin lineaarinen haku ei vaadi lajiteltuja elementtejä, joten elementit voidaan lisätä helposti luettelon loppuun.
- Lineaarinen haku on helppokäyttöinen, eikä tilattuja elementtejä tarvita. Toisaalta binäärisen haun algoritmi on kuitenkin hankala, ja elementit on järjestetty välttämättä järjestyksessä.
johtopäätös
Sekä lineaariset että binääriset hakualgoritmit voivat olla hyödyllisiä sovelluksesta riippuen. Kun taulukko on tietorakenne ja elementit on järjestetty lajitellussa järjestyksessä, binäärinen haku on edullinen pikahakua varten . Jos linkitetty luettelo on datarakenne riippumatta siitä, miten elementit on järjestetty, lineaarinen haku hyväksytään binäärisen hakualgoritmin suoran toteutuksen puuttumisen vuoksi.
Tyypillistä binäärisen haun algoritmia ei voida käyttää linkitetylle listalle, koska linkitetty lista on luonteeltaan dynaaminen eikä tiedetä, missä keskielementti todella on osoitettu. Näin ollen on olemassa vaatimus suunnitella binäärisen hakualgoritmin muunnos, joka voi toimia myös linkitetyssä luettelossa, koska binäärinen haku on nopeampi suorituksessa kuin lineaarinen haku.
