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. Tas meklē noteiktu vērtību sarakstā, pārbaudot katru saraksta elementu. Binārā meklēšana ir arī metode, ko izmanto, lai noteiktu vērtību atrastu sakārtotā sarakstā. Binārā meklēšanas metode uz pusi samazina pārbaudīto elementu skaitu (katrā atkārtojumā), samazinot laiku, kas vajadzīgs, lai sarakstā atrastu doto vienumu.
Kas ir lineārā meklēšana?
Lineārā meklēšana ir vienkāršākā meklēšanas metode, kas katru saraksta elementu pārbauda secīgi, līdz atrod noteiktu elementu. Lineārās meklēšanas metodes ievade ir secība (piemēram, masīvs, kolekcija vai virkne) un vienums, kas jāmeklē. Izeja ir patiesa, ja norādītais vienums 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ā tas pirms visiem elementiem atrod nepieciešamo elementu. Lineārās meklēšanas sarežģītība ir o (n). Tāpēc tiek uzskatīts par pārāk lēnu, 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 noteiktu elementu atrastu 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 nekā vidējais elements, tas atkal sāk metodi, izmantojot tikai sakārtotā saraksta apakšējo pusi. Ja meklētais elements ir mazāks par vidējo elementu, tas atkal sāk metodi, izmantojot tikai sakārtotā saraksta augšējo pusi. Ja meklētais elements neatrodas 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āto elementu skaitu (katrā atkārtojumā) atkarībā no salīdzināšanas rezultāta. Sekojoši,binārā meklēšana notiek logaritmiskā laikā, iegūstot o (log n) vidējo gadījumu veiktspēju.
Kāda ir atšķirība starp bināro meklēšanu un lineāro meklēšanu?
Lai gan gan lineārā meklēšana, 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, laineru meklēšana var darboties arī nešķirotos sarakstos. Kārtojot sarakstu, vidējā gadījumu sarežģītība ir n log n. lineārā meklēšana ir vienkārša un saprotama, nekā binārā meklēšana. Bet lineārā meklēšana ir pārāk lēna, lai to varētu izmantot ar lieliem sarakstiem, jo tā vidējā veiktspēja ir o (n). No otras puses, binārā meklēšana tiek uzskatīta par efektīvāku metodi, ko varētu izmantot ar lieliem sarakstiem. Bet binārās meklēšanas ieviešana varētu būt diezgan sarežģīta, un pētījums ir parādījis, ka precīzu binārā meklēšanas kodu varēja atrast tikai piecās no divdesmit grāmatām.
