{{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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: A\̲[̲d] \le x \le A\…

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á $O(n)$.

• binární: NEXT := $\left\lceil {d+h \over 2} \right\rceil$. Půlíme interval. Očekávaný i nejhorší počet dotazů je $O(\log n)$.

• interpolační: NEXT :=

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 29: …il(h - d){x - A\̲[̲d] \over A\[h] …

  . 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č $O(\log \log n)$ (nedokazuje se), nejhorší $O(n/2)$.

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 $c=\sqrt{h-d+1}$, 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á $O(\log n)$. 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 $O(\log \log n)$, ukazuje se, že to druhé je konstantní! Takže očekávaná složitost je $O(\log \log n)$.

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 $1/i^2$, jejíž součet je z analýzy konečný.

{{TODO|důkaz pořádně}}