Kahendotsing
Kahendotsing ehk binaarotsing on otsingualgoritm, mis võtab sisendiks sorteeritud järjendi ja otsitava väärtuse ning väljastab väärtuse asukoha järjendis või teatab, et seda väärtust järjendis ei leidu. Algoritmi alguses võetakse vahemikuks, millest väärtust otsitakse, terve järjend, ning igal sammul otsitakse väärtust edasi alamvahemikust, milles on algse vahemiku keskmisest elemendist kas kõik väiksemad või kõik suuremad elemendid. Alamvahemik valitakse selle järgi, kas otsitav väärtus on väiksem või suurem kui algse vahemiku keskmine element. Kui vahemiku keskmine element on võrdne otsitava väärtusega, siis see väärtus on leitud. Kui aga vahemik on tühi, siis otsitavat väärtust järjendis ei leidu. Kahendotsingu poolt ühe väärtuse leidmiseks sooritatav võrdluste arv on halvimal juhul O ( log ⁡ n ) {\displaystyle O(\log n)} , kus n {\displaystyle n} on järjendi elementide arv ning O {\displaystyle O} tähistab asümptootilist hinnangut. Otsingu käigus algoritmi kasutatava mälu hulk ei muutu. See on üldjuhul optimaalne väärtuse otsimiseks sorteeritud järjendist võrdluste abil, mis tuleneb võrdlemistega sorteerimise ajalise keerukuse alumisest piirist O ( n log ⁡ n ) {\displaystyle O(n\log n)} . On palju kahendotsinguga sarnaseid algoritme, näiteks eksponentsiaalne otsing, mille sisend võib olla piiramatu (dünaamiliselt genereeritud) suurusega. Kahendotsingupuud ja B-puud on samuti tihedalt seotud kahendotsinguga.