Mis on binaarne otsing?

Oletame, et inimesel on väga suur sortiment esemeid ja ta paigutab need mingil kindlal viisil pikka ritta. See isik saab binaarotsingu abil kiiresti aru saada, kus reas konkreetne objekt asub. See otsing tehakse nii, et kontrollitakse rea keskmist üksust ja kui keskmine objekt ei ole otsitav, siis vaadatakse seejärel ainult ühte rea pooltest, kus üksus võiks olla. Inimene teaks, millises pooles edasi vaadata, sest esemed on järjestatud. Neid kahte sammu tehakse ikka ja jälle, järjest väiksematel poolikutel, kuni ese kas leitakse või pole enam kuskilt otsida.

Arvutiteaduse valdkonnas on kahendotsing samm-sammult protseduur, mis leiab järjestikku sorteeritud andmekogus oleva üksuse asukoha või indeksi. See saavutab selle, võrreldes teadaolevat väärtust massiivi määratud keskmise elemendiga ja kui see ei ole samaväärne, piirab keskmise elemendi võrdlust korduvalt komplekti väiksema asjakohase poolega, kuni saadakse ekvivalents või loend on ammendatud.

Binaarne otsing, mida mõnikord nimetatakse ka poole intervalliga otsinguks, on palju kiirem kui tavaline järjestikune otsing, mis algab üksuste loendi ühest otsast ja võrdleb iga üksust, kuni leitakse vaste või kuni otsing jõuab otsingu lõpuni. nimekiri. Kui inimesel oli järjest 100 üksust ja otsiti viimane üksus, kuluks järjestikuse otsingu jaoks 100 võrdlust. Poolitamise meetod nõuab aga kõige rohkem seitset võrdlust enne üksuse leidmist. See on ilmselt palju tõhusam kui järjestikune otsing.

Binaarse otsingu suurim puudus on see, et selle otsingu toimimiseks tuleb üksuste loendit sorteerida. Loendi sortimine võtab aega. Sortimine ja seejärel seda tüüpi otsingut kasutades võib võtta rohkem aega kui teist tüüpi otsingu tegemine.

Võimalus kasutada teavet, eriti väga suurtest andmekogumitest, on oluline paljude eluülesannete täitmiseks. Arvutiteaduse distsipliin tegeleb mitut tüüpi probleemidega, sealhulgas tõhusate viiside leidmisega teabe otsimiseks, et saada kasulikke tulemusi. Binaarne otsing on vaid üks paljudest andmete otsimiseks saadaolevatest algoritmidest.