Pirms apgūstam bināro meklēšanu, iemācīsimies:
Kas ir meklēšana?
Meklēšana ir utilīta, kas ļauj tās lietotājam atrast dokumentus, failus, datu nesējus vai jebkura cita veida datus, kas atrodas datu bāzē. Meklēšana darbojas pēc vienkārša principa - kritērijus saskaņot ar ierakstiem un parādīt lietotājiem. Tādā veidā darbojas visvienkāršākā meklēšanas funkcija.
Kas ir binārā meklēšana?
Binārā meklēšana ir uzlabots meklēšanas algoritma veids, kas atrod un ienes datus no sakārtotā vienumu saraksta. Tā pamatdarbības princips ir datu sadalīšana uz pusi, līdz vajadzīgā vērtība tiek atrasta un parādīta lietotājam meklēšanas rezultātos. Binārā meklēšana parasti tiek dēvēta par pusintervāla meklēšanu vai logaritmisko meklēšanu .
Šajā algoritma apmācībā jūs uzzināsiet:
- Kas ir meklēšana?
- Kas ir binārā meklēšana?
- Kā darbojas binārā meklēšana?
- Binārās meklēšanas piemērs
- Kāpēc mums ir nepieciešama binārā meklēšana?
Kā darbojas binārā meklēšana?
Binārā meklēšana darbojas šādā veidā:
- Meklēšanas process sākas, atrodot sakārtotā datu masīva vidējo elementu
- Pēc tam galveno vērtību salīdzina ar elementu
- Ja atslēgas vērtība ir mazāka par vidējo elementu, meklēšanā tiek analizētas vidējā elementa augšējās vērtības, lai tās salīdzinātu un saskaņotu
- Gadījumā, ja atslēgas vērtība ir lielāka par vidējo elementu, meklēšanā tiek analizētas vidējā elementa zemākās vērtības salīdzināšanai un saskaņošanai
Binārās meklēšanas piemērs
Apskatīsim vārdnīcas piemēru. Ja jums jāatrod noteikts vārds, neviens neiziet katru vārdu secīgi, bet nejauši atrod tuvākos vārdus, lai meklētu vajadzīgo vārdu.
Šis attēls ilustrē sekojošo:
- Jums ir 10 ciparu masīvs, un jāatrod elements 59.
- Visi elementi ir atzīmēti ar indeksu no 0 līdz 9. Tagad tiek aprēķināts masīva vidus. Lai to izdarītu, jūs ņemat indeksa kreiso un labo vērtību un dalāt tās ar 2. Rezultāts ir 4,5, bet mēs ņemam zemāko vērtību. Tādējādi vidus ir 4.
- Algoritms nomet visus elementus no vidus (4) līdz zemākajai robežai, jo 59 ir lielāks par 24, un tagad masīvā paliek tikai 5 elementi.
- Tagad 59 ir lielāks par 45 un mazāks par 63. Vidējais ir 7. Tādējādi labā indeksa vērtība kļūst vidēja - 1, kas ir vienāda ar 6, un kreisā indeksa vērtība paliek tāda pati kā iepriekš, kas ir 5.
- Šajā brīdī jūs zināt, ka 59 nāk pēc 45. Tādējādi kreisais indekss, kas ir 5, kļūst arī vidējs.
- Šīs iterācijas turpinās, līdz masīvs tiek samazināts tikai līdz vienam elementam, vai arī atrodamais vienums kļūst par masīva vidu.
2. piemērs
Apskatīsim šo piemēru, lai saprastu, kā darbojas binārā meklēšana
- Jums ir sakārtotu vērtību masīvs, kas svārstās no 2 līdz 20, un jums ir jāatrod 18.
- Apakšējās un augšējās robežas vidējā vērtība ir (l + r) / 2 = 4. Meklētā vērtība ir lielāka par vidējo, kas ir 4.
- Masīva vērtības, kas ir mazākas par vidu, tiek izmestas no meklēšanas, un tiek meklētas vērtības, kas lielākas par vidējo vērtību 4.
- Šis ir atkārtots dalīšanas process, līdz tiek atrasts faktiskais meklējamais vienums.
Kāpēc mums ir nepieciešama binārā meklēšana?
Šie iemesli padara bināro meklēšanu par labāku izvēli, ko izmantot kā meklēšanas algoritmu:
- Binārā meklēšana efektīvi darbojas uz sakārtotiem datiem neatkarīgi no datu lieluma
- Tā vietā, lai veiktu meklēšanu, secīgi izejot caur datiem, binārais algoritms nejauši piekļūst datiem, lai atrastu nepieciešamo elementu. Tas padara meklēšanas ciklus īsākus un precīzākus.
- Binārā meklēšana veic sakārtoto datu salīdzināšanu, pamatojoties uz secības principu, nevis izmantojot vienlīdzības salīdzinājumus, kas ir lēnāki un lielākoties neprecīzi.
- Pēc katra meklēšanas cikla algoritms masīva lielumu sadala uz pusi, tāpēc nākamajā atkārtojumā tas darbosies tikai atlikušajā masīva pusē
Kopsavilkums
- Meklēšana ir utilīta, kas ļauj tās lietotājam meklēt dokumentus, failus un cita veida datus. Binārā meklēšana ir uzlabots meklēšanas algoritma veids, kas atrod un ienes datus no sakārtotā vienumu saraksta.
- Binārā meklēšana parasti tiek dēvēta par pusintervāla meklēšanu vai logaritmisko meklēšanu
- Tas darbojas, sadalot masīvu uz pusēm katrā atkārtojumā, kas atrodams vajadzīgajā elementā.
- Binārais algoritms aizņem masīva vidu, dalot kreisās un labākās rādītāja vērtību summu ar 2. Tagad algoritms nomet elementu apakšējo vai augšējo robežu no masīva vidus, atkarībā no atrodamā elementa .
- Algoritms nejauši piekļūst datiem, lai atrastu nepieciešamo elementu. Tas padara meklēšanas ciklus īsākus un precīzākus.
- Binārajā meklēšanā tiek kārtoti sakārtoti dati, pamatojoties uz secības principu, nevis izmantojot lēnas un neprecīzas vienlīdzības salīdzinājumus.
- Binārā meklēšana nav piemērota nešķirotiem datiem.