Binārās un lineārās meklēšanas atšķirība

Binārā meklēšana vs lineārā meklēšana

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 atrastu noteiktu vērtību sakārtotā sarakstā. Binārā meklēšanas metode uz pusi samazina pārbaudīto elementu skaitu (katrā atkārtojumā), 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 secīgi pārbauda katru saraksta elementu, līdz tas atrod noteiktu elementu. Ievade lineārās meklēšanas metodē ir secība (piemēram, masīvs, kolekcija vai virkne) un vienums, kas jāmeklē. Izeja ir patiesa, ja norādītais vienums atrodas norādītajā secībā, vai nepatiesa, ja tā nav secībā. Tā kā šī metode pārbauda katru saraksta vienību, līdz tiek atrasts norādītais, sliktākajā gadījumā tā iziet visus saraksta elementus, pirms atrod nepieciešamo elementu. Lineārās meklēšanas sarežģītība ir o (n). Tāpēc tiek uzskatīts, ka tas tiek izmantots pārāk lēni, 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, 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. Rezultātā binārā meklēšana notiek logaritmiskajā laikā, iegūstot o (log n) gadījuma vidējo veiktspēju.

Kāda ir atšķirība starp bināro meklēšanu un lineāro meklēšanu?

Pat ja lineārā meklēšana un binārā meklēšana ir meklēšanas metodes, tām ir vairākas atšķirības. Kamēr binārā meklēšana darbojas sakārtotajos sarakstos, līnijpārvadātāju meklēšana var darboties arī nešķirotajos sarakstos. Kārtojot sarakstu, parasti lietu vidējā 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 lielos sarakstos, ņemot vērā o (n) gadījuma vidējo veiktspēju. No otras puses, binārā meklēšana tiek uzskatīta par efektīvāku metodi, kuru varētu izmantot lielos sarakstos. Bet binārā meklēšanas ieviešana varētu būt diezgan sarežģīta, un pētījums parādīja, ka precīzu binārā meklēšanas kodu varēja atrast tikai piecās no divdesmit grāmatām.