Kahendotsing: erinevus redaktsioonide vahel

Olgu järjendi <code>J</code> mõne vahemiku esimese, keskmise ja viimase elemendi [[nullipõhine indekseerimine|nullipõhised indeksid]] vastavalt <code>e</code>, <code>k</code> ja <code>v</code> ning otsitav väärtus <code>o</code>. Kahendotsingust võib olla lihtsam aru saada [[rekursioon|rekursiivsel]] kujul, kus alamvahemikust saab korduvalt algne vahemik:

 

Kui e > v:

J ei sisalda o

k = alumine_täisosa((e + v) / 2)

Kui o < J[k]:

Kui o > J[k]:

tagasta k

 

(Reaalarvu [[Täis- ja murdosa|alumine täisosa]] on suurim täisarv, mis ei ole sellest reaalarvust suurem.) Algsest vahemikust <code>[e, v]</code> saab sõltuvalt väärtustest <code>o</code> ja <code>J[k]</code> kas <code>[e, k-1]</code> või <code>[k+1, v]</code>. Kui järjendi <code>J</code> elementide arv on <code>n</code>, siis tervest järjendist väärtuse otsimiseks kutsume funktsiooni vahemikuga <code>[0, n-1]</code>:

 

 

Tuleb märkida, et rekursiivne versioon kahendotsingust võib kasutada <math>O(\log n)</math> 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: <ref name=":0" />

 

e = 0

v = n - 1

k = alumine_täisosa((e + v) / 2)

v = k - 1

Muidu kui J[k] < o: