Glavna razlika med linearnim iskanjem in binarnim iskanjem je, da binarno iskanje traja manj časa za iskanje elementov iz razvrščenega seznama elementov. Iz tega izhaja, da je učinkovitost binarne metode iskanja večja od linearnega iskanja.
Druga razlika med obema je, da je predpogoj za binarno iskanje, tj. Elemente je treba razvrstiti, medtem ko v linearnem iskanju ni takega predpogoja. Čeprav oba načina iskanja uporabljata različne tehnike, ki so obravnavane spodaj.
Primerjalna tabela
| Podlaga za primerjavo | Linearno iskanje | Binarno iskanje |
|---|---|---|
| Časovna kompleksnost | O (N) | O (log 2 N) |
| Najboljši primer | Prvi element O (1) | Sredinski element O (1) |
| Predpogoj za polje | Ni potrebno | Polje mora biti urejeno |
| Najslabši primer za N število elementov | Potrebnih je N primerjav | Lahko zaključi po samo 2 primerjavah log |
| Lahko se izvaja na | Vrstica in povezani seznam | Ne morem se neposredno izvajati na povezanem seznamu |
| Vstavite operacijo | Preprosto vstavite na konec seznama | Zahtevajte, da se obdelava vstavi na ustrezno mesto, da se ohrani razvrščeni seznam. |
| Vrsta algoritma | Iterativna po naravi | Razdelite in osvojite v naravi |
| Uporabnost | Enostavna uporaba in ni potrebe po naročenih elementih. | Vsakokrat težaven algoritem in elementi morajo biti urejeni po vrstnem redu. |
| Vrstice kode | Manj | Več |
Opredelitev linearnega iskanja
Pri linearnem iskanju se vsak element matrike po eni pridobiva v logičnem zaporedju in preveri, ali je želen element ali ne. Iskanje bo neuspešno, če bodo dostopni vsi elementi, in želenega elementa ni mogoče najti. V najslabšem primeru bo število povprečnega primera, ki ga bomo morda morali pregledati, pol velikosti matrike (n / 2).
Zato lahko linearno iskanje definiramo kot tehniko, ki zaporedoma prečka niz, da najde dano postavko. Spodnji program prikazuje iskanje elementa matrike z uporabo iskanja.
Učinkovitost linearnega iskanja
Poraba časa ali število primerjav, opravljenih pri iskanju zapisa v iskalni tabeli, določa učinkovitost tehnike. Če je želeni zapis prisoten v prvem položaju tabele iskanja, se izvede samo ena primerjava. Ko je želeni zapis zadnji, potem je treba narediti n primerjav. Če je zapis prisoten nekje v iskalni tabeli, bo povprečno število primerjav (n + 1/2). Najslabši možni izkoristek te tehnike je O (n) za vrstni red izvedbe.
C Program za iskanje elementa z linearno tehniko iskanja.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("vnesite število elementa:"); scanf ("% d", & n); printf ("Vnesite številke: n"); za (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("vnesite številko, ki jo želite iskati:"); scanf ("% d", & item); za (i = 0; i = 0) {printf ("n% d najdemo na položaju% d:", item, loc + 1); } else {printf ("ne obstaja"); } getch (); } Opredelitev binarnega iskanja
Binarno iskanje je izjemno učinkovit algoritem. Ta tehnika iskanja porabi manj časa pri iskanju podane postavke pri najmanjših možnih primerjavah. Za binarno iskanje moramo najprej razvrstiti elemente matrike.
Logika te tehnike je podana spodaj:
- Najprej poiščite srednji element matrike.
- Srednji element matrike se primerja z elementom, ki ga iščemo.
Obstajajo trije primeri:
- Če je element zahtevani element, je iskanje uspešno.
- Ko je element manjši od želenega elementa, poiščite samo prvo polovico polja.
- Če je večji od želenega elementa, poiščite v drugi polovici polja.
Enake korake ponovite, dokler ne najdete elementa ali izpraznite v iskalnem območju. V tem algoritmu se zmanjša vsako območje iskanja časa. Zato je število primerjav največ log (N + 1). Kot rezultat je učinkovit algoritem v primerjavi z linearnim iskanjem, vendar mora biti polje razvrščeno pred binarnim iskanjem.
C Program za iskanje elementa z binarno tehniko iskanja.
#include void main () {int i, beg, konec, sredina, n, iskanje, niz [100]; printf ("Vnesite število elementov n"); scanf ("% d", & n); printf ("Vnesite% d številke n", n); za (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Vnesite številko za iskanje n"); scanf ("% d", & iskanje); beg = 0; konec = n - 1; sredina = (prijava + konec) / 2; while (beg <= end) {if (matrika [sredina] konec) printf ("Iskanje je neuspešno!% d ni na seznamu. \ t getch (); } Ključne razlike med linearnim iskanjem in binarnim iskanjem
- Linearno iskanje je po naravi iterativno in uporablja sekvenčni pristop. Po drugi strani pa binarno iskanje izvaja razdelitev in osvajanje.
- Časovna kompleksnost linearnega iskanja je O (N), medtem ko je binarno iskanje O (log 2 N).
- Najboljši čas v linearnem iskanju je prvi element, tj. O (1). V nasprotju z binarnim iskanjem je to za srednji element, tj. O (1).
- V linearnem iskanju je najslabši primer za iskanje elementa N število primerjav. V nasprotju s tem pa je število binarnih iskanj log 2 N.
- Linearno iskanje se lahko izvede tako v matriki kot tudi v povezanem seznamu, medtem ko binarnega iskanja ni mogoče izvajati neposredno na povezanem seznamu.
- Kot vemo Binarno iskanje zahteva razvrščeno matriko, ki je razlog. Za obdelavo je potrebno vstaviti na ustrezno mesto za vzdrževanje razvrščenega seznama. Nasprotno, linearno iskanje ne zahteva razvrščenih elementov, zato se elementi enostavno vstavijo na konec seznama.
- Linearno iskanje je preprosto za uporabo in ni potrebe po naročenih elementih. Po drugi strani pa je binarni iskalni algoritem zapleten, elementi pa so nujno urejeni.
Zaključek
Oba linearna in binarna iskalna algoritma sta lahko uporabna, odvisno od aplikacije. Kadar je matrika podatkovna struktura, in elementi so razvrščeni po vrstnem redu, je za hitro iskanje prednostno binarno iskanje. Če je povezan seznam podatkovna struktura, ne glede na to, kako so razvrščeni elementi, je linearno iskanje sprejeto zaradi nedostopnosti neposredne implementacije binarnega algoritma iskanja.
Tipičnega binarnega iskalnega algoritma ni mogoče uporabiti za povezani seznam, ker je povezan seznam dinamičen po naravi in ni znano, kje je dejansko dodeljen srednji element. Zato obstaja potreba po oblikovanju variacije binarnega iskalnega algoritma, ki lahko deluje tudi na povezanem seznamu, ker je binarno iskanje hitrejše kot linearno iskanje.
