Kahendotsing: erinevus redaktsioonide vahel

Kahendotsing ehk binaarotsing on [[otsingualgoritm]], mis võtab sisendiks [sorteeritud[sortimisalgoritm | sortimisalgoritmsorteeritud]] [järjendi[järjend | järjendjärjendi]] ja otsitava väärtuse ning väljastab väärtuse asukohta 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. Alamvahemikku 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 ei leidu järjendis. [Knuth]

Võrdluste arv, mida kahendotsing sooritab ühe väärtuse leidmiseks, on halvimal juhul <math>O(\log n)</math>, kus <math>n</math> on järjendi elementide arv ja <math>O</math> tähistab [asümptootilist[algoritmiline hinnangutkeerukus | algoritmilineasümptootilist keerukushinnangut]]. Seejuures kasutab kahendotsing konstantse mälu hulga. See on üldjuhul optimaalne väärtuse otsimiseks sorteeritud järjendist võrdluste abil, mis tuleneb võrdlemistega sorteerimise ajalise keerukuse alumisest piirist <math>O(n \log n)</math>.

On palju kahendotsinguga sarnaseid algoritme, näiteks [[eksponentsiaalne otsing]], mille sisend võib olla piiramatu (dünaamiliselt genereeritud) suurusega. [Kahendotsingupuud[kahendotsingupuu | kahendotsingupuuKahendotsingupuud]] ja [[B-puudpuu | B-puu]] on samuti tihedalt seotud kahendotsinguga. [?]

Olgu järjendi <code>J</code> mõne vahemiku esimese, keskmise ja viimase elemendi [nullipõhised[nullipõhine indeksidindekseerimine | nullipõhinenullipõhised indekseerimineindeksid]] 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 [rekursiivsel[rekursioon | rekursioonrekursiivsel]] kujul, kus alamvahemikust saab korduvalt algne vahemik:

(Reaalarvu [alumine täisosa | [Täis-_ja_murdosa | alumine täisosa]] on suurim täisarv, mis ei ole sellest reaalarvust suurem.)

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 ([[en:tail call | ''tail-call optimization'' | en: tail call]]). Selle tõttu võib olla efektiivsem iteratiivne versioon:

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 <code>[e, v]</code> keskmise elemendiga <code>J[k]</code> ja on suurem keskmisest elemendist, siis see peab olema suurem ka kõikidest elementidest vahemikus <code>[e, k]</code>, sest järjend on sorteeritud ning elemendid vahemikus <code>[e, k]</code> 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 <code>[k, v]</code>, 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 <code>[k+1, v]</code> või <code>[e, k-1]</code>, mis ongi vahemik, kus kahendotsing jätkub. [Matemaatilise[matemaatiline induktsiooniinduktsioon | matemaatilineMatemaatilise induktsiooninduktsiooni]] tõttu kahendotsing alati otsib väärtust vahemikust, kus ta leidub, kui järjend sisaldab seda väärtust.

<math>O(\log n)</math> 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 <math>O(\log n)</math> võrdlust, siis selle abil saaks sorteerida <math>n</math> elemendiga järjendit vähem kui <math>O(n\log n)</math> võrdlusega halvimal juhul, mis on tegelikult võimatu. Selleks teeme uue järjendi <math>S</math>, mis on alguses tühi, ning sisestame sellesse ühekaupa kõik järjendi <math>J</math> elemendid nii, et see jääks sorteerituks. Kui järjendisse <math>S</math> on juba sisestatud <math>m</math> elementi, siis leiame hüpoteetilise otsingualgoritmi abil vähem kui <math>O(\log m)</math> võrdlusega koha, kuhu sisestada <code>J[m]<\/code>, nii et järjend <math>S</math> jääks sorteerituks – teatame ebaõnnestunud otsingu lõpus koha, kust väärtust viimasena otsiti. Kui oleme korranud seda indeksist <math>m=0</math> kuni <math>m=n-1</math>, siis <math>S</math> on sorteeritud, sest igal sammul me säilitasime selle elementide järjekorda, ning <math>S</math> sisaldab kõiki järjendi <math>J</math> elemente, mistõttu oleme sorteerinud järjendit <math>J</math>. Me kasutasime võrdlusi ainult sisestamise koha leidmiseks, mistõttu võrdluste arv on kokku vähem kui <math>O(0) + \sum_{m=1}^{n-1} O(\log m) = O(\log (n-1)!) = O(n\log n)<\/math>, sest logaritmide summa on korrutise logaritm ning <math>O(\log(n!)) = O(n\log n)<\/math> [Stirlingi valemi | Faktoriaal#Stirlingi_valem] kohaselt. Tegelikult see on võimatu, mistõttu kahendotsing kasutab optimaalset võrdluste arvu halvimal juhul. [cmp sort]

Eksponentsiaalne otsing on sarnane kahendotsinguga, aga alustab otsimist vahemikust <code>[0, 1]<\/code> 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.