Pirms izprast atšķirības starp lineāro un bināro meklēšanu, mums vispirms būtu atsevišķi jāzina lineārā meklēšana un binārā meklēšana.
Kas ir lineārā meklēšana?
Lineāro meklēšanu sauc arī par secīgu meklēšanu, kas vienkārši skenē katru elementu vienlaikus. Pieņemsim, ka mēs vēlamies meklēt elementu masīvā vai sarakstā; mēs vienkārši aprēķinām tā garumu un nelecam ne pie viena priekšmeta.
Apskatīsim vienkāršu piemēru.
Pieņemsim, ka mums ir 10 elementu masīvs, kā parādīts zemāk esošajā attēlā:
Iepriekš redzamajā attēlā parādīts rakstzīmju tipu masīvs ar 10 vērtībām. Ja mēs vēlamies meklēt 'E', tad meklēšana sākas no 0thelementu un skenē katru elementu, līdz elements, t.i., “E” netiek atrasts. Mēs nevaram tieši pārlēkt no 0thelements uz 4thelements, t.i., katrs elements tiek skenēts pa vienam, līdz elements netiek atrasts.
Lineārās meklēšanas sarežģītība
Lineārā meklēšana skenē katru elementu pa vienam, līdz elements netiek atrasts. Ja elementu skaits palielinās, tiek palielināts arī skenējamo elementu skaits. Mēs varam teikt, ka laiks, kas nepieciešams elementu meklēšanai, ir proporcionāls elementu skaitam . Tāpēc sliktākā gadījuma sarežģītība ir O (n)
Kas ir binārā meklēšana?
Binārā meklēšana ir meklēšana, kurā tiek aprēķināts vidējais elements, lai pārbaudītu, vai tas ir mazāks vai lielāks par meklējamo elementu. Galvenā binārās meklēšanas izmantošanas priekšrocība ir tā, ka tā nepārbauda katru saraksta elementu. Tā vietā, lai skenētu katru elementu, tā veic meklēšanu līdz saraksta pusei. Tātad, binārā meklēšana aizņem mazāk laika, lai meklētu elementu, salīdzinot ar lineāro meklēšanu.
Vienīgais binārās meklēšanas priekšnoteikums ir tāds, ka masīvam ir jābūt sakārtotam secībā, savukārt lineārā meklēšana darbojas gan kārtotā, gan nešķirotā masīvā. Binārās meklēšanas algoritms ir balstīts uz sadali un iekaro tehniku, kas nozīmē, ka tas sadalīs masīvu rekursīvi.
Binārajā meklēšanā tiek izmantoti trīs gadījumi:
1. gadījums: dati
2. gadījums: dati>a[vid], pēc tam pa labi=vidus-1
3. gadījums: dati = a[mid] // elements ir atrasts
Iepriekš minētajā gadījumā ' a ' ir masīva nosaukums, vidus ir elementa indekss, kas aprēķināts rekursīvi, datus ir elements, kas ir jāmeklē, pa kreisi apzīmē masīva kreiso elementu un pa labi apzīmē elementu, kas atrodas masīva labajā pusē.
Izpratīsim binārās meklēšanas darbību, izmantojot piemēru.
Pieņemsim, ka mums ir 10 izmēru masīvs, kas ir indeksēts no 0 līdz 9, kā parādīts zemāk esošajā attēlā:
Mēs vēlamies meklēt 70 elementu no iepriekš minētā masīva.
1. darbība: Pirmkārt, mēs aprēķinām masīva vidējo elementu. Mēs ņemam vērā divus mainīgos, t.i., kreiso un labo. Sākotnēji pa kreisi = 0 un pa labi = 9, kā parādīts zemāk esošajā attēlā:
Vidējā elementa vērtību var aprēķināt šādi:
Tāpēc mid = 4 un a[mid] = 50. Meklējamais elements ir 70, tāpēc a[mid] nav vienāds ar datiem. 2. gadījums ir apmierināts, t.i., dati>a[vid.].
2. darbība: Kā dati>a[vid], tā kreisā vērtība tiek palielināta par vidu+1, t.i., left=mid+1. Vidēja vērtība ir 4, tāpēc kreisā vērtība kļūst par 5. Tagad mēs esam ieguvuši apakšgrupu, kā parādīts zemāk esošajā attēlā:
Tagad atkal vidējā vērtība tiek aprēķināta, izmantojot iepriekš minēto formulu, un vidējā vērtība kļūst par 7. Tagad vidējo vērtību var attēlot kā:
Iepriekš redzamajā attēlā mēs varam novērot, ka a[mid]>data, tāpēc atkal nākamajā darbībā tiks aprēķināta vidējā vērtība.
3. darbība: Kā a[vid]>dati, tiesību vērtība tiek samazināta līdz 1. vidum. Vidēja vērtība ir 7, tāpēc labās vērtības vērtība kļūst par 6. Masīvu var attēlot kā:
Vidējā vērtība tiks aprēķināta vēlreiz. Kreisās un labās puses vērtības ir attiecīgi 5 un 6. Tāpēc vidējā vērtība ir 5. Tagad vidu var attēlot masīvā, kā parādīts zemāk:
Iepriekš redzamajā attēlā mēs varam novērot, ka a[vid]
4. darbība: Kā [vid.] Tagad vidējā vērtība tiek aprēķināta vēlreiz, izmantojot formulu, kuru mēs jau apspriedām. Kreisās un labās puses vērtības ir attiecīgi 6 un 6, tāpēc vidējā vērtība kļūst par 6, kā parādīts zemāk esošajā attēlā: Iepriekš redzamajā attēlā varam novērot, ka a[mid]=data. Tāpēc meklēšana ir pabeigta, un elements ir veiksmīgi atrasts. Tālāk ir norādītas atšķirības starp lineāro meklēšanu un bināro meklēšanu. Apraksts Lineārā meklēšana ir meklēšana, kas atrod elementu sarakstā, meklējot elementu secīgi, līdz elements tiek atrasts sarakstā. No otras puses, binārā meklēšana ir meklēšana, kas rekursīvi atrod saraksta vidējo elementu, līdz vidējais elements tiek saskaņots ar meklēto elementu. Abu meklējumu darbība Lineārā meklēšana sāk meklēšanu no pirmā elementa un skenē vienu elementu vienlaikus, nepārlecot uz nākamo elementu. No otras puses, binārā meklēšana sadala masīvu uz pusēm, aprēķinot masīva vidējo elementu. Īstenošana Lineāro meklēšanu var īstenot jebkurā lineārā datu struktūrā, piemēram, vektorā, atsevišķi saistītajā sarakstā, dubultā saistītajā sarakstā. Turpretim bināro meklēšanu var ieviest tajās datu struktūrās ar divvirzienu pārvietošanos, t.i., pārvietošanos uz priekšu un atpakaļ. Sarežģītība Lineāro meklēšanu ir viegli lietot, vai arī mēs varam teikt, ka tā ir mazāk sarežģīta, jo lineārās meklēšanas elementus var sakārtot jebkurā secībā, savukārt binārajā meklēšanā elementi ir jāsakārto noteiktā secībā. Sakārtoti elementi Lineārās meklēšanas elementus var sakārtot nejaušā secībā. Lineārajā meklēšanā elementiem nav obligāti jābūt sakārtotiem sakārtotā secībā. Savukārt binārajā meklēšanā elementi ir jāsakārto sakārtotā secībā. To var sakārtot vai nu augošā, vai dilstošā secībā, un attiecīgi tiks mainīts arī algoritms. Tā kā binārajā meklēšanā tiek izmantots sakārtots masīvs, elements ir jāievieto pareizajā vietā. Turpretim lineārajai meklēšanai nav nepieciešams sakārtots masīvs, lai jauno elementu varētu viegli ievietot masīva beigās. Pieeja Lineārajā meklēšanā elementa atrašanai tiek izmantota iteratīva pieeja, tāpēc to sauc arī par secīgu pieeju. Turpretim binārā meklēšana aprēķina masīva vidējo elementu, tāpēc tā izmanto sadali un iekaro pieeju. Datu kopa Lineārā meklēšana nav piemērota lielai datu kopai. Ja mēs vēlamies meklēt elementu, kas ir pēdējais masīva elements, lineārā meklēšana sāks meklēšanu no pirmā elementa un turpinās līdz pēdējam elementam, tāpēc elementa meklēšanas laiks būs liels. No otras puses, binārā meklēšana ir piemērota lielai datu kopai, jo tā aizņem mazāk laika. Ātrums Ja datu kopa ir liela lineārajā meklēšanā, tad skaitļošanas izmaksas būtu augstas un ātrums kļūst lēns. Ja datu kopa ir liela binārajā meklēšanā, tad skaitļošanas izmaksas būtu mazākas, salīdzinot ar lineāro meklēšanu, un ātrums kļūst ātrs. Izmēri Lineāro meklēšanu var izmantot gan vienas, gan daudzdimensiju masīvā, savukārt bināro meklēšanu var īstenot tikai viendimensijas masīvā. Efektivitāte Lineārā meklēšana ir mazāk efektīva, ja ņemam vērā lielas datu kopas. Lielu datu kopu gadījumā binārā meklēšana ir efektīvāka par lineāro meklēšanu. Apskatīsim atšķirības tabulas veidā. 
Atšķirības starp lineāro meklēšanu un bināro meklēšanu
binārā koka šķērsošana pēc kārtas
Salīdzināšanas pamats Lineārā meklēšana Binārā meklēšana Definīcija Lineārā meklēšana sāk meklēšanu no pirmā elementa un salīdzina katru elementu ar meklēto elementu, līdz elements netiek atrasts. Tā atrod meklētā elementa pozīciju, atrodot masīva vidējo elementu. Sakārtoti dati Lineārajā meklēšanā elementi nav jāsakārto sakārtotā secībā. Binārās meklēšanas priekšnosacījums ir tāds, ka elementi ir jāsakārto sakārtotā secībā. Īstenošana Lineāro meklēšanu var īstenot jebkurā lineārā datu struktūrā, piemēram, masīvā, saistītajā sarakstā utt. Binārās meklēšanas ieviešana ir ierobežota, jo to var ieviest tikai tajās datu struktūrās, kurām ir divvirzienu šķērsošana. Pieeja Tas ir balstīts uz secīgu pieeju. Tā pamatā ir 'skaldi un valdi' pieeja. Izmērs Tas ir vēlams maza izmēra datu kopām. Tas ir vēlams liela izmēra datu kopām. Efektivitāte Tas ir mazāk efektīvs liela izmēra datu kopu gadījumā. Tas ir efektīvāks liela izmēra datu kopu gadījumā. Sliktākajā gadījumā Lineārā meklēšanā sliktākais scenārijs elementa atrašanai ir O(n). Binārajā meklēšanā sliktākais scenārijs elementa atrašanai ir O(log2n). Labākais scenārijs Lineārā meklēšanā vislabākais scenārijs pirmā elementa atrašanai sarakstā ir O(1). Binārajā meklēšanā vislabākais scenārijs pirmā elementa atrašanai sarakstā ir O(1). Izmēru masīvs To var ieviest gan vienā, gan daudzdimensiju masīvā. To var ieviest tikai daudzdimensiju masīvā.