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 formula_1, kus formula_2 on järjendi elementide arv ning formula_3 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 formula_4. 
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.
Algoritmi kirjeldus.
Olgu järjendi codice_1 mõne vahemiku esimese, keskmise ja viimase elemendi nullipõhised indeksid vastavalt codice_2, codice_3 ja codice_4 ning otsitav väärtus codice_5. Kahendotsingust võib olla lihtsam aru saada rekursiivsel kujul, kus alamvahemikust saab korduvalt algne vahemik:
 funktsioon kahendotsing(o, J, e, v):
 Kui e &gt; v:
 J ei sisalda o
 k = alumine_täisosa((e + v) / 2)
 Kui o &lt; J[k]:
 tagasta kahendotsing(o, J, e, k - 1)
 Kui o &gt; J[k]:
 tagasta kahendotsing(o, J, k + 1, v)
 tagasta k
(Reaalarvu alumine täisosa on suurim täisarv, mis ei ole sellest reaalarvust suurem.) Algsest vahemikust codice_6 saab sõltuvalt väärtustest codice_5 ja codice_8 kas codice_9 või codice_10. Kui järjendi codice_1 elementide arv on codice_12, siis tervest järjendist väärtuse otsimiseks kutsume funktsiooni vahemikuga codice_13:
codice_14. 
Tuleb märkida, et rekursiivne versioon kahendotsingust võib kasutada formula_1 mälu, mitte optimaalse konstantse mälu hulga, kui funktsiooni pinumälu ei vabastata enne rekursiivset väljakutset ("tail call optimization"). Selle tõttu võib olla efektiivsem iteratiivne versioon: 
 funktsioon kahendotsing(o, J):
 e = 0
 v = n - 1
 Korda:
 Kui e &gt; v:
 J ei sisalda o
 k = alumine_täisosa((e + v) / 2)
 Kui o &lt; J[k]:
 v = k - 1
 Muidu kui J[k] &lt; o:
 e = k + 1
 Muidu:
 tagasta k
Korrektsus.
Näitame, et kui otsitav väärtus leidub järjendis, siis see on alati vahemikus, kust kahendotsing otsib seda. Algses vahemikus on kõik järjendi elemendid, nii et kui otsitav väärtus leidub, siis see peab olema nende hulgas. Kui väärtus leidub vahemikus codice_6 keskmise elemendiga codice_8 ja on suurem keskmisest elemendist, siis see peab olema suurem ka kõikidest elementidest vahemikus codice_17, sest järjend on sorteeritud ning elemendid vahemikus codice_17 on väiksemad keskmisest elemendist või võrdsed sellega. Analoogiliselt, kui otsitav väärtus on väiksem keskmisest elemendist, siis see peab olema väiksem ka kõikidest elementidest vahemikus codice_19, mis on omakorda keskmisest elemendist suuremad või sellega võrdsed. Järelikult uus vahemik, kus võib leiduda otsitava väärtus, on vastavalt kas codice_10 või codice_9, mis ongi vahemik, kus kahendotsing jätkub. Matemaatilise induktsiooni järgi otsib kahendotsing alati väärtust vahemikust, kus ta leidub, kui järjend sisaldab seda väärtust.
Lisaks näeme, et vahemikud codice_9 ja codice_10 mõlemad sisaldavad vähem elemente kui eelmine vahemik codice_6, mistõttu vahemik, kus kahendotsing toimub, läheb pidevalt väiksemaks ning muutub tühjaks lõpliku aja jooksul, kui väärtust ei leita enne seda. Järelikult lõpetab kahendotsing alati töö lõpliku aja jooksul. 
Keerukus.
Kahendotsing sooritab ühe väärtuse leidmiseks halvimal juhul formula_6 võrdlust, kus formula_7 tähistab alamtäisosa. 
formula_1 on vähim võimalik võrdluste arv halvimal juhul algoritmi jaoks, mis otsib sorteeritud järjendist ühe väärtuse võrdluste abil. Kui oleks selline algoritm, mis kasutaks vähem kui formula_1 võrdlust, siis selle abil saaks sorteerida formula_2 elemendiga järjendit vähem kui formula_11 võrdlusega halvimal juhul, mis on tegelikult võimatu. Selleks teeme uue järjendi formula_12, mis on alguses tühi, ning sisestame sellesse ühekaupa kõik järjendi formula_13 elemendid nii, et see jääks sorteerituks. Kui järjendisse formula_12 on juba sisestatud formula_15 elementi, siis leiame hüpoteetilise otsingualgoritmi abil vähem kui formula_16 võrdlusega koha, kuhu sisestada codice_25, nii et järjend formula_12 jääks sorteerituks – teatame ebaõnnestunud otsingu lõpus koha, kust väärtust viimasena otsiti. Kui oleme korranud seda indeksist formula_18 kuni formula_19, siis formula_12 on sorteeritud, sest igal sammul me säilitasime selle elementide järjekorda, ning formula_12 sisaldab kõiki järjendi formula_13 elemente, mistõttu oleme sorteerinud järjendit formula_13. Me kasutasime võrdlusi ainult sisestamise koha leidmiseks, mistõttu võrdluste arv on kokku vähem kui formula_24sest logaritmide summa on korrutise logaritm ning formula_25 Stirlingi valemi kohaselt. Tegelikult see on võimatu, mistõttu kahendotsing kasutab optimaalset võrdluste arvu halvimal juhul. 
Saame otsemini näidata optimaalsust vaadeldes otsingualgoritme, millel on formula_26 võimalikku tulemust ning mis kasutavad nendeni jõudmiseks ainult kahe võimaliku tulemusega otsuseid. Kahendotsing on selline algoritm, sest see kasutab tulemuse valimiseks ainult võrdluseid, millel on kaks võimalikku tulemust – üks väärtus on teisest väiksem või mitte – ning kahendotsingul on formula_27 võimalikku tulemust, sest tulemus on kas väärtuse indeks või et väärtus ei leidu. See tähendab, et iga otsingualgoritm on alguses ühes olekus ning peab lõpus olema sõltuvalt sisenditest ühes formula_26 erinevast olekust. See vastab puule, mille tipud on algoritmi olekud ning lõigud on olekumuutused, mis võivad toimuda pärast mõnda otsust. Puu on tsükliteta, sest algoritm lõpetab iga sisendi puhul töö lõpliku aja jooksul. Puu on kahendpuu ehk igal tipul on kas 0 või 2 last, sest algoritm lõpetab töö või teeb järgmise tipuni jõudmiseks kahe võimaliku tulemusega otsust. Juurtipp on tipp, kus algoritm alustab töö. On olemas tee juurtipu ja iga lehe vahel, sest algoritmi alguses on võimalikud kõik formula_26 tulemust. Algoritmi otsuste arv halvimal juhul on maksimaalne lõikude arv teel juurtipu ja mõne lehe vahel. Käesoleva formula_26 lehega kahendpuu puhul lõikude arv teel on väikseim, kui puu on tasakaalus, ja on vähemalt formula_31. Järelikult otsuste arv ehk võrdlustega otsimise puhul vähim võrdluste arv halvimal juhul on vähemalt formula_1. 
Informatsiooniteoreetiliselt tähendab see, et algoritm saab iga otsusega ühe bitti informatsiooni juurde ning tulemus – kahendotsingu puhul indeks – sisaldab formula_33 bitti informatsiooni, mistõttu tulemuse saamiseks on vaja vähemalt formula_33 otsust. 
Võrdlus teiste algoritmidega.
Eksponentsiaalne otsing on sarnane kahendotsinguga, aga alustab otsimist vahemikust codice_26 ja kahekordistab vahemiku viimase elemendi indeksit kuni vahemik sisaldab otsitavat väärtust või teatab, et järjend ei sisalda seda väärtust. Kui vahemik sisaldab väärtust, siis seda leitakse kahendotsinguga. Eksponentsiaalne otsing kasutab halvimal juhul rohkem võrdlusi kui kahendotsing, kuid võib olla efektiivsem, kui otsitav väärtus on tihti järjendi alguses.
Kahendotsingupuud ja B-puud kasutavad sarnaselt kahendotsinguga võrdlusi elementide välistamiseks, mis on kas kõik väiksemad või suuremad mõne tipu väärtusest. Kui puu on tasakaalus, siis sellesse väärtuse sisestamise ajalise keerukuse hinnang on formula_1 halvimal juhul, mis on väiksem kui sorteeritud järjendisse sisestamise ajalise keerukuse hinnang formula_36 halvimal juhul. Samas kui puu ei ole tasakaalus, siis see võib kasutada ühe väärtuse otsimisel kuni formula_36 võrdlust halvimal juhul.
Erinevalt eelmistest andmestruktuuridest kasutavad paisktabelid võrdluste asemel paiskfunktsiooni ja põrgete tõrjet väärtuse otsimiseks. Paiskfunktsiooni sisenditeks on väärtused, mida sisestame paisktabelisse – need ei pea olema arvud, vaid võivad olla ka näiteks sõned – ja väljunditeks on indeksid paisktabelisisesesse järjendisse. Paisktabelist väärtuse leidmiseks kulub keskmiselt konstantne aeg ning ideaalse paiskamise korral kulub ka halvimal juhul konstantne aeg. See on võimalik, sest kui paisktabelis on formula_2 elementi, siis paiskfunktsioon teeb sisuliselt formula_2 võimaliku tulemusega otsust ühekorraga, erinevalt kahendotsingust, mis teeb iga võrdlusega ainult kahe võimaliku tulemusega otsust. Samas paisktabeli efektiivsus sõltub tugevalt paiskfunktsiooni valikust ning kui ideaalne paiskamine ei ole võimalik, siis ühe väärtuse otsimise ajalise keerukuse hinnang võib olla kuni formula_36 halvimal juhul.