Galvenā atšķirība starp lineāro meklēšanu un bināro meklēšanu ir tā, ka binārā meklēšana aizņem mazāk laika, lai meklētu elementu no sakārtotā elementu saraksta. Tātad tiek secināts, ka binārās meklēšanas metodes efektivitāte ir lielāka nekā lineārā meklēšana.
Vēl viena atšķirība starp abām ir tā, ka binārajai meklēšanai ir priekšnoteikums, ti, elementiem jābūt sakārtotiem, bet lineārajā meklēšanā šāda priekšnoteikuma nav. Lai gan abas meklēšanas metodes izmanto dažādas metodes, kas aplūkotas turpmāk.
Salīdzinājuma diagramma
| Salīdzināšanas pamats | Lineārā meklēšana | Binārā meklēšana |
|---|---|---|
| Laika sarežģītība | O (N) | O (log 2 N) |
| Labākais gadījuma laiks | Pirmais elements O (1) | Centra elements O (1) |
| Priekšnoteikums masīvam | Nav nepieciešams | Array ir jābūt sakārtotam |
| Sliktākais gadījums N elementu skaitam | Ir nepieciešami N salīdzinājumi | Var secināt tikai pēc 2 N salīdzinājumiem |
| Var tikt īstenots | Sarakstu un saistīto sarakstu saraksts | Nevar tieši īstenot saistīto sarakstu |
| Ievietojiet darbību | Viegli ievietot saraksta beigās | Nepieciešama apstrāde, lai ievietotu to pareizajā vietā, lai saglabātu sakārtotu sarakstu. |
| Algoritma tips | Iteratīvs raksturs | Sadaliet un iekarojiet dabā |
| Noderīgums | Viegli lietojams un nav nepieciešams pasūtīts elements. | Jebkurā gadījumā būtu jāorganizē sarežģīts algoritms un elementi. |
| Kodu rindas | Mazāk | Vairāk |
Lineārās meklēšanas definīcija
Lineārā meklēšanā katrs masīva elements tiek iegūts pa vienam loģiskā secībā un pārbaudīts, vai tas ir vēlamais elements. Meklēšana būs neveiksmīga, ja būs pieejami visi elementi, un vēlamais elements nav atrasts. Sliktākajā gadījumā vidējā gadījuma skaits, kas mums var būt nepieciešams, lai skenētu pusi no masīva lieluma (n / 2).
Tāpēc lineāro meklēšanu var definēt kā paņēmienu, kas secīgi pārvieto masīvu, lai atrastu konkrēto objektu. Turpmāk norādītā programma ilustrē masīva elementa meklēšanu, izmantojot meklēšanu.
Lineārās meklēšanas efektivitāte
Laika patēriņš vai salīdzinājumu skaits, kas veikti, meklējot ierakstu meklēšanas tabulā, nosaka tehnikas efektivitāti. Ja meklēšanas tabulas pirmajā pozīcijā ir vēlamais ieraksts, tad tiek veikts tikai viens salīdzinājums. Kad vēlamais ieraksts ir pēdējais, tad ir jāveic n salīdzinājumi. Ja ieraksts ir jāiesniedz kaut kur meklēšanas tabulā, salīdzinājumu skaits būs (n + 1/2). Šīs metodes sliktākā efektivitāte ir O (n), kas nozīmē izpildes kārtību.
C Programma, lai meklētu elementu ar lineāru meklēšanas tehniku.
#include #include void main () {int a [100], n, i, vienums, loc = -1; clrscr (); printf ("Ievadiet elementa skaitu:"); scanf ("% d", un n); printf ("Ievadiet ciparus: n"); (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("Ievadiet meklējamo numuru:"); scanf ("% d", un vienums); (i = 0; i = 0) {printf ("n% d tiek atrasts pozīcijā% d:", vienums, loc + 1); } else {printf ("Vienums nav"); } getch (); } Binārā meklēšanas definīcija
Binārā meklēšana ir ļoti efektīvs algoritms. Šī meklēšanas metode patērē mazāk laika, meklējot konkrēto objektu minimālos iespējamos salīdzinājumos. Lai veiktu bināro meklēšanu, vispirms mums ir jāizšķir masīva elementi.
Šīs metodes loģika ir dota tālāk:
- Pirmkārt, atrodiet masīva vidējo elementu.
- Masīva vidējais elements tiek salīdzināts ar meklējamo elementu.
Var rasties trīs gadījumi:
- Ja elements ir vajadzīgais elements, tad meklēšana ir veiksmīga.
- Kad elements ir mazāks par vēlamo vienumu, tad meklējiet tikai masīva pirmo pusi.
- Ja tas ir lielāks par vēlamo elementu, tad meklējiet otrajā pusē.
Atkārtojiet tās pašas darbības, līdz meklēšanas apgabalā tiek atrasts elements vai izplūst. Šajā algoritmā katru reizi, kad meklēšanas apgabals samazinās. Tāpēc salīdzinājumu skaits ir lielākais log (N + 1). Tā rezultātā tas ir efektīvs algoritms, salīdzinot ar lineāro meklēšanu, bet masīvs ir jāklasificē pirms binārā meklēšanas.
C Programma, lai atrastu elementu ar bināro meklēšanas tehniku.
#include void main () {int i, beg, end, vidū, n, meklēšana, masīvs [100]; printf ("Ievadiet elementa skaitu"); scanf ("% d", un n); printf ("Ievadiet% d skaitļus n", n); (i = 0; i <n; i ++) scanf ("% d", un masīvs [i]); printf ("Ievadiet meklējamo numuru"); scanf ("% d" un meklēšana); beg = 0; end = n - 1; vidū = (beg + end) / 2; kamēr (beg <= end) {if (masīvs [vidū] beigas) printf ("meklēšana ir neveiksmīga!% d nav sarakstā. \ t getch (); } Galvenās atšķirības starp lineāro meklēšanu un bināro meklēšanu
- Lineārā meklēšana pēc būtības ir iteratīva un izmanto secīgu pieeju. No otras puses, binārā meklēšana īsteno dalīšanas un iekarošanas pieeju.
- Lineārās meklēšanas laika sarežģītība ir O (N), bet binārajai meklēšanai ir O (log 2 N).
- Labākais gadījuma laiks lineārajā meklēšanā ir pirmajam elementam, ti, O (1). Saistībā ar bināro meklēšanu tas ir vidējam elementam, ti, O (1).
- Lineārajā meklēšanā vissliktākais elements elementa meklēšanai ir N salīdzinājuma numurs. Turpretī tas ir log 2 N salīdzinājuma numurs binārajai meklēšanai.
- Lineāro meklēšanu var īstenot gan masīvā, gan saistītā sarakstā, bet bināro meklēšanu nevar īstenot tieši saistītajā sarakstā.
- Kā zināms, binārajai meklēšanai ir nepieciešams sakārtots masīvs, kas ir iemesls. Nepieciešama apstrāde, lai ievietotu pareizajā vietā, lai saglabātu sakārtotu sarakstu. Gluži pretēji, lineārai meklēšanai nav vajadzīgi sakārtoti elementi, tāpēc elementi ir viegli ievietojami saraksta beigās.
- Lineāro meklēšanu ir viegli izmantot, un nav nepieciešami nekādi pasūtītie elementi. No otras puses, bināro meklēšanas algoritms tomēr ir grūts, un elementi vienmēr ir sakārtoti kārtībā.
Secinājums
Atkarībā no lietojumprogrammas var būt noderīgi gan lineārie, gan binārie meklēšanas algoritmi. Ja masīvs ir datu struktūra un elementi sakārtoti sakārtotā secībā, ātrai meklēšanai ieteicams veikt bināru meklēšanu. Ja saistītais saraksts ir datu struktūra neatkarīgi no tā, kā elementi ir sakārtoti, lineārā meklēšana tiek pieņemta, jo nav iespējams veikt bināro meklēšanas algoritmu.
Tipisko bināro meklēšanas algoritmu nevar izmantot piesaistītajam sarakstam, jo saistītais saraksts ir dinamisks un nav zināms, kur faktiski ir piešķirts vidējais elements. Līdz ar to ir prasība izstrādāt binārā meklēšanas algoritma variāciju, kas var darboties arī ar saistīto sarakstu, jo binārā meklēšana ir ātrāka izpildē nekā lineārā meklēšana.
