Prieš mokydamiesi dvejetainės paieškos, mokykimės:
Kas yra paieška?
Paieška yra įrankis, leidžiantis jo vartotojui rasti dokumentus, failus, laikmenas ar bet kokio kito tipo duomenis, saugomus duomenų bazėje. Paieška veikia pagal paprastą kriterijų suderinimo su įrašais principą ir pateikimą vartotojui. Tokiu būdu veikia paprasčiausia paieškos funkcija.
Kas yra dvejetainė paieška?
Dvejetainė paieška yra išplėstinis paieškos algoritmo tipas, kuris suranda ir pateikia duomenis iš surūšiuoto elementų sąrašo. Pagrindinis jo veikimo principas yra padalinti duomenis iš sąrašo į pusę, kol reikiama reikšmė bus surasta ir rodoma vartotojui paieškos rezultatuose. Dvejetainė paieška paprastai žinoma kaip pusės intervalo paieška arba logaritminė paieška .
Šioje algoritmo pamokoje sužinosite:
- Kas yra paieška?
- Kas yra dvejetainė paieška?
- Kaip veikia dvejetainė paieška?
- Dvejetainės paieškos pavyzdys
- Kodėl mums reikia dvejetainės paieškos?
Kaip veikia dvejetainė paieška?
Dvejetainė paieška veikia tokiu būdu:
- Paieškos procesas pradedamas surandant surūšiuoto duomenų masyvo vidurinį elementą
- Po to pagrindinė vertė palyginama su elementu
- Jei rakto vertė yra mažesnė nei vidurinis elementas, tada ieškant analizuojamos viršutinio vidurinio elemento vertės, kad būtų galima palyginti ir suderinti
- Jei pagrindinė vertė yra didesnė už vidurinį elementą, tada ieškoma analizuojant apatines vidurinio elemento vertes, kad būtų galima palyginti ir suderinti
Dvejetainės paieškos pavyzdys
Pažvelkime į žodyno pavyzdį. Jei jums reikia rasti tam tikrą žodį, niekas neperžiūri kiekvieno žodžio nuosekliai, bet atsitiktinai suranda artimiausius žodžius norimo žodžio paieškai.
Ankstesnis vaizdas iliustruoja:
- Turite 10 skaitmenų masyvą, todėl reikia rasti elementą 59.
- Visi elementai pažymėti indeksu nuo 0 iki 9. Dabar apskaičiuojamas masyvo vidurys. Norėdami tai padaryti, paimkite kairę ir dešinę indekso reikšmes ir padalykite jas iš 2. Rezultatas yra 4,5, bet mes atsižvelgiame į žemiausią vertę. Taigi vidurys yra 4.
- Algoritmas numeta visus elementus nuo vidurio (4) iki žemiausios ribos, nes 59 yra didesnis nei 24, o dabar masyve liko tik 5 elementai.
- Dabar 59 yra didesnis nei 45 ir mažesnis nei 63. Vidurys yra 7. Taigi dešinioji indekso reikšmė tampa vidurinė - 1, kuri lygi 6, o kairiosios indekso reikšmė išlieka tokia pati kaip anksčiau, tai yra 5.
- Šiuo metu jūs žinote, kad 59 eina po 45. Taigi kairysis indeksas, kuris yra 5, taip pat tampa viduriu.
- Šios iteracijos tęsiasi tol, kol masyvas bus sumažintas tik iki vieno elemento, arba randamas elementas taps masyvo viduriu.
2 pavyzdys
Pažvelkime į šį pavyzdį, kad suprastume, kaip veikia dvejetainė paieška
- Turite išrūšiuotų verčių masyvą nuo 2 iki 20 ir turite rasti 18.
- Apatinės ir viršutinės ribų vidurkis yra (l + r) / 2 = 4. Ieškoma vertė yra didesnė už vidurį, kuris yra 4.
- Masyvo vertės, mažesnės už vidurį, iš paieškos atmetamos, o didesnės nei 4 vidurio vertės - ieškoma.
- Tai yra pasikartojantis dalijimo procesas, kol bus rastas faktinis daiktas, kurio bus ieškoma.
Kodėl mums reikia dvejetainės paieškos?
Dėl šių priežasčių dvejetainė paieška yra geresnis pasirinkimas naudoti kaip paieškos algoritmą:
- Dvejetainė paieška efektyviai veikia surūšiuotus duomenis, neatsižvelgiant į duomenų dydį
- Užuot atlikęs paiešką, eidamas duomenis iš eilės, dvejetainis algoritmas atsitiktinai patenka į duomenis, kad rastų reikiamą elementą. Tai daro paieškos ciklus trumpesnius ir tikslesnius.
- Dvejetainėje paieškoje atliekami rūšiuojami duomenys lyginami pagal tvarkos principą, o ne naudojant lygybės palyginimus, kurie yra lėtesni ir dažniausiai netikslūs.
- Po kiekvieno paieškos ciklo algoritmas masyvo dydį padalija į pusę, taigi kitoje iteracijoje jis veiks tik likusioje masyvo pusėje
Santrauka
- Paieška yra įrankis, leidžiantis jo vartotojui ieškoti dokumentų, failų ir kitų tipų duomenų. Dvejetainė paieška yra išplėstinis paieškos algoritmo tipas, kuris suranda ir pateikia duomenis iš surūšiuoto elementų sąrašo.
- Dvejetainė paieška paprastai žinoma kaip pusės intervalo paieška arba logaritminė paieška
- Jis veikia dalijant masyvą į pusę kiekvienoje iteracijoje pagal reikiamą elementą.
- Dvejetainis algoritmas užima masyvo vidurį, padalydamas kairiosios ir dešiniosios indekso reikšmių sumą iš 2. Dabar algoritmas numato apatinę arba viršutinę elementų ribą nuo masyvo vidurio, priklausomai nuo elemento, kurį reikia rasti .
- Algoritmas atsitiktine tvarka pasiekia duomenis, norėdamas rasti reikiamą elementą. Tai daro paieškos ciklus trumpesnius ir tikslesnius.
- Dvejetainė paieška atlieka rūšiuojamų duomenų palyginimus pagal tvarkos principą, o ne lygių lygybės palyginimų, kurie yra lėti ir netikslūs.
- Dvejetainė paieška nėra tinkama nerūšiuotiems duomenims.