Ieteicams, 2020

Redaktora Izvēle

Atšķirība starp lineāro meklēšanu un bināro meklēšanu

Lineārā meklēšana un binārā meklēšana ir divas metodes, ko izmanto masīvos elementu meklēšanai . Meklēšana ir process, kurā atrasts elements elementu sarakstā, kas tiek glabāts jebkurā secībā vai nejauši.

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 pamatsLineārā meklēšanaBinārā meklēšana
Laika sarežģītībaO (N)O (log 2 N)
Labākais gadījuma laiksPirmais elements O (1)Centra elements O (1)
Priekšnoteikums masīvamNav nepieciešamsArray ir jābūt sakārtotam
Sliktākais gadījums N elementu skaitamIr nepieciešami N salīdzinājumiVar secināt tikai pēc 2 N salīdzinājumiem
Var tikt īstenotsSarakstu un saistīto sarakstu sarakstsNevar tieši īstenot saistīto sarakstu
Ievietojiet darbībuViegli ievietot saraksta beigāsNepieciešama apstrāde, lai ievietotu to pareizajā vietā, lai saglabātu sakārtotu sarakstu.
Algoritma tipsIteratīvs rakstursSadaliet un iekarojiet dabā
NoderīgumsViegli lietojams un nav nepieciešams pasūtīts elements.Jebkurā gadījumā būtu jāorganizē sarežģīts algoritms un elementi.
Kodu rindasMazākVairā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:

  1. Ja elements ir vajadzīgais elements, tad meklēšana ir veiksmīga.
  2. Kad elements ir mazāks par vēlamo vienumu, tad meklējiet tikai masīva pirmo pusi.
  3. 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

  1. 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.
  2. Lineārās meklēšanas laika sarežģītība ir O (N), bet binārajai meklēšanai ir O (log 2 N).
  3. 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).
  4. 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.
  5. 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ā.
  6. 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.
  7. 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.

Top