Kahendotsing: erinevus redaktsioonide vahel

Kahendotsing ehk binaarotsing on [[otsingualgoritm]], mis võtab sisendiks [[sortimisalgoritm | sorteeritud]] [[järjend | jä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. [Knuth1]

[Knuth1][cmpsort2]

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

Kahendotsing sooritab ühe väärtuse leidmiseks halvimal juhul <math>\lfloor(\log n)+1 \rfloor \in O(\log n)</math> võrdlust, kus <math> \lfloor\cdot\rfloor</math> tähistab alamtäisosa. [Knuth1]

<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 sort2]

[[informatsiooniteooria | Informatsiooniteoreetiliselt]] see tähendab, et algoritm saab iga otsusega ühe bitti informatsiooni juurde ning tulemus – kahendotsingu puhul indeks – sisaldab <math>O(\log T)</math> bitti informatsiooni, mistõttu tulemuse saamiseks on vaja vähemalt <math>O(\log T)</math> otsust. [?]

Erinevalt eelmistest andmestruktuuridest kasutavad [[paisktabel | paisktabelid]] võrdluste asemel [paiskfunktsiooni[räsifunktsioon | räsifunktsioonpaiskfunktsiooni]] ja [[räsifunktsioon#kollisioonitõrje | 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õne (andmetüüp) | sõned]] – ja väljunditeks on indeksid paisktabelisisesesse järjendisse. Paisktabelist väärtuse leidmiseks kulub keskmiselt konstantne aeg ning [[räsifunktsioon#ideaalne räsimine | ideaalse paiskamise]] korral kulub ka halvimal juhul konstantne aeg. See on võimalik, sest kui paisktabelis on <math>n</math> elementi, siis paiskfunktsioon teeb sisuliselt <math>n</math> 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 <math>O(n)</math> halvimal juhul.