{{TIN066 Skripta}}
Množina S je reprezentována v setříděném poli A (délky n), hledáme daný prvek; mám ''kraje'' d, h, vím, že hledaný prvek x je <math>A[d] \le x \le A[h]</math>. Kraje postupně přibližuji k sobě, když se potkají, našel jsem prvek.
Zaveďme si pomocnou operaci NEXT, ta vrátí novou hodnotu kraje (kterého? snadno poznáme porovnáním). Podle konkrétní podoby NEXT rozlišujeme několik druhů vyhledávání:
* '''unární''': NEXT := d+1. Prostě jedeme popořadě, očekávaný počet dotazů je n/2, ale nejhorší n, tedy to trvá <math>O(n)</math>.
* '''binární''': NEXT := <math>\left\lceil {d+h \over 2} \right\rceil</math>. Půlíme interval. Očekávaný i nejhorší počet dotazů je <math>O(\log n)</math>.
* '''interpolační''': NEXT := <math>d + \left\lceil(h - d){x - A[d] \over A[h] - A[d]}\right\rceil</math>. Přes kraje protáhneme přímku a píchneme tam, kde by na ní mělo být x. Očekávaný počet dotazů je kdovíproč <math>O(\log \log n)</math> (nedokazuje se), nejhorší <math>O(n/2)</math>.
== Zobecněné kvadratické vyhledávání ==
...je taková strašlivá zdivočelost. Chtěli bychom zkombinovat binární a interpolační vyhledávání tak, abychom měli pěknou očekávanou i nejhorší složitost. Myšlenka spočívá v tom, že si vždy v našem rozsahu interpolačním dotazem vytyčíme výchozí bod hledání, postavíme velikost unárního skoku <math>c=\sqrt{h-d+1}</math>, a z výchozího bodu pak střídavě putujeme binárními a unárními dotazy ve směru x, dokud není unární skok větší než velikost úseku - v té chvíli znovu položíme interpolační dotaz, atd.
Co na to složitost? V nejhorším případě se rozdíl h-d sníží na polovinu během tří kroků, to znamená <math>O(\log n)</math>. Očekávaná složitost je očekávaný počet intepolačních dotazů krát očekávaný počet dotazů v jednom interpolačním kroku. To prvé již víme že je <math>O(\log \log n)</math>, ukazuje se, že to druhé je konstantní! Takže očekávaná složitost je <math>O(\log \log n)</math>.
Idea konstantnosti: Zjistíme, že počet prvků na začátku úseku menších než x sleduje binomické rozdělení; známe i jeho rozptyl atd., tedy můžeme použít Čebyševovu nerovnost, ta nám dá řadu <math>1/i^2</math>, jejíž součet je z analýzy konečný.
{{TODO|důkaz pořádně}}
