Binārā meklēšana pret lineāro meklēšanu
Lineārā meklēšana, kas pazīstama arī kā secīgā meklēšana, ir vienkāršākais meklēšanas algoritms. Tā meklē noteiktu vērtību sarakstā, pārbaudot katru elementu sarakstā. Binārā meklēšana ir arī metode, ko izmanto, lai sakārtotu sarakstā noteiktu vērtību atrastu. Binārā meklēšanas metode uz pusi samazina pārbaudīto elementu skaitu (katrā iterācijā), samazinot laiku, kas nepieciešams, lai sarakstā atrastu doto vienumu.
Kas ir lineārā meklēšana?
Lineārā meklēšana ir vienkāršākā meklēšanas metode, kas pārbauda katru saraksta elementu secīgi, līdz tiek atrasts noteikts elements. Lineārās meklēšanas metodes ievade ir secība (piemēram, masīvs, kolekcija vai virkne) un vienums, kas jāmeklē. Izvade ir patiesa, ja norādītā vienība ir norādītajā secībā, vai nepatiesa, ja tā nav secībā. Tā kā šī metode pārbauda katru saraksta vienumu, līdz tiek atrasts norādītais vienums, sliktākajā gadījumā tā izies cauri visiem saraksta elementiem, pirms tā atradīs vajadzīgo elementu. Lineārās meklēšanas sarežģītība ir o(n). Tāpēc tiek uzskatīts, ka tas ir pārāk lēns, lai to izmantotu, meklējot elementus lielos sarakstos. Bet tas ir ļoti vienkārši un vieglāk īstenojams.
Kas ir binārā meklēšana?
Binārā meklēšana ir arī metode, ko izmanto, lai atrastu noteiktu vienumu sakārtotā sarakstā. Šī metode sākas ar meklētā elementa salīdzināšanu ar elementiem saraksta vidū. Ja salīdzinājums nosaka, ka abi elementi ir vienādi, metode apstājas un atgriež elementa pozīciju. Ja meklētais elements ir lielāks par vidējo elementu, tā atsāk metodi, izmantojot tikai sakārtotā saraksta apakšējo pusi. Ja meklētais elements ir mazāks par vidējo elementu, tā atsāk metodi, izmantojot tikai sakārtotā saraksta augšējo pusi. Ja meklētais elements nav sarakstā, metode atgriezīs unikālu vērtību, kas to norāda. Tāpēc binārā meklēšanas metode uz pusi samazina salīdzināmo elementu skaitu (katrā iterācijā) atkarībā no salīdzināšanas rezultāta. Līdz ar to binārā meklēšana tiek veikta logaritmiskā laikā, kā rezultātā tiek iegūta o(log n) vidējā gadījuma veiktspēja.
Kāda ir atšķirība starp bināro meklēšanu un lineāro meklēšanu?
Lai gan gan lineārā, gan binārā meklēšana ir meklēšanas metodes, tām ir vairākas atšķirības. Kamēr binārā meklēšana darbojas sakārtotos sarakstos, līnijpārvadātāju meklēšana var darboties arī nešķirotos sarakstos. Saraksta kārtošanai parasti ir vidējā gadījuma sarežģītība n log n. Lineārā meklēšana ir vienkārša un viegli īstenojama nekā binārā meklēšana. Taču lineārā meklēšana ir pārāk lēna, lai to izmantotu lielos sarakstos, jo tās o(n) vidējā gadījuma veiktspēja. No otras puses, binārā meklēšana tiek uzskatīta par efektīvāku metodi, ko varētu izmantot lielos sarakstos. Taču binārās meklēšanas ieviešana varētu būt diezgan sarežģīta, un pētījums parādīja, ka precīzu kodu binārajai meklēšanai var atrast tikai piecās no divdesmit grāmatām.
