Hledání polohy v tabulce

Máme tabulku $N$ hodnot $x_i$ setříděnou podle velikosti.
Pro dané $x$ hledáme do kterého podintervalu $\left< x_{i}, x_{i+1}\right)$ patří.

Hledání polohy náhodně zadaných bodů $x$

Postupné prohledání nevýhodné - $N$ operací (nejhůře), $N/2$ průměrně

Výhodná strategie - půlení intervalu indexů - $\sim \log_2 N$ operací

Postup - Vezmeme index $[N/2]$ a porovnáme $x$ a $x_{[N/2]}$.
Je-li $x < x_{[N/2]}$, pak porovnat $x$ a $x_{[N/4]}$, je-li $x > x_{[N/2]}$, pak porovnat $x$ a $x_{[3N/4]}$.

Algoritmus

      klo := 1; khi := N;
      while (khi-klo) > 1 do begin
         knew = (khi+klo) div 2;
         if (x < x[knew]) then khi := knew else klo := knew
      end;

Posloupnost zadávaných bodů
Předchozí postup je vhodný pouze pro náhodnou posloupnost bodů. Pokud jsou zadávány body $x$ postupně podle velikosti, je výhodné zahájit hledání v intervalu, kde ležel předchozí bod a pak v sousedních intervalech.