binaarotsingut

Binaarotsing, tuntud ka kui poolitusotsing, on efektiivne algoritm, mida kasutatakse sorteeritud massiivis või loendis elemendi leidmiseks. Selle peamine eelis seisneb selle ajalisest keerukusest, mis on O(log n), mis tähendab, et otsinguaeg kasvab väga aeglaselt massiivi suurusega.

Algoritmi töö põhineb pideval massiivi keskmise elemendi võrdlemisel otsitava väärtusega. Kui keskmine element on võrdne otsitava väärtusega, on otsing edukas. Kui otsitav väärtus on väiksem keskmisest elemendist, jätkub otsing massiivi esimeses pooles. Kui otsitav väärtus on suurem keskmisest elemendist, jätkub otsing massiivi teises pooles. Seda protsessi korratakse seni, kuni element leitakse või kuni otsitav ala muutub tühjaks, mis tähendab, et elementi massiivis ei ole.

Binaarotsingu kasutamiseks on rangelt vajalik, et andmestruktuur oleks eelnevalt sorteeritud. Sorteerimata andmetel binaarotsingu rakendamine annab valesid või mittetäielikke tulemusi. Selle tõhusus muudab selle populaarseks valikuks paljudes rakendustes, kus tuleb kiiresti otsida suures koguses sorteeritud andmeid.