Turinys:
Apibrėžimas - ką reiškia dvejetainė paieška?
Dvejetainis paieškos algoritmas naudojamas norint rasti konkrečios vertės, esančios išrūšiuotame masyve, vietą. Šis paieškos algoritmas, veikiantis padalijimo ir užkariavimo principu, gali būti gana greitas, tačiau perspėjimas yra tas, kad duomenys turi būti surūšiuotos formos. Tai veikia pradedant paiešką masyvo viduryje ir einant žemyn pirmąja apatine arba viršutine sekos puse. Jei mediana yra mažesnė už tikslinę, tai reiškia, kad paieška turi būti didesnė, jei ne, tada ji turi būti nukreipta į mažėjančią masyvo dalį.
Dvejetainė paieška taip pat žinoma kaip pusiau intervalo arba logaritminė paieška.
„Techopedia“ paaiškina dvejetainę paiešką
Dvejetainė paieška yra greitas ir efektyvus būdas rasti konkrečią tikslinę vertę iš užsakytų daiktų rinkinio. Pradėjęs išrūšiuoto sąrašo viduryje, jis gali efektyviai perpjauti paieškos plotą per pusę, nuspręsdamas, ar pakilti, ar nusileisti nuo sąrašo, remiantis vidutine verte, palyginti su tiksline verte.
Pvz., Kai tikslinė vertė yra 8 ir paieškos vieta yra nuo 1 iki 11:
- Rasti mediana / vidurkio reikšmė ir nustatyti rodyklę, kuri šiuo atveju yra 6.
- Tikslas 8 lyginamas su 6. Kadangi 6 yra mažesnis nei 8, tikslas turi būti aukštesnėje pusėje.
- Rodyklė perkeliama į kitą vertę (7) ir lyginama su taikiniu. Jis yra mažesnis, todėl rodyklė pereina į kitą didesnę vertę.
- Rodyklė dabar yra 8. Palyginus tai su taikiniu, tai tikslus tikslumas, todėl taikinys rastas.
Naudojant dvejetainę paiešką, taikinį reikėjo palyginti tik su trimis vertėmis. Palyginus su linijine paieška, ji būtų buvusi pradėta nuo pat pirmosios vertės ir pajudėta aukštyn, turint palyginti taikinį su aštuoniomis vertėmis. Dvejetainė paieška įmanoma tik su užsakytu duomenų rinkiniu; Jei duomenys būtų išdėstyti atsitiktine tvarka, linijinė paieška duotų rezultatų visą laiką, o dvejetainė paieška greičiausiai būtų įstrigusi begalinėje kilpoje.
