Máme tabulku hodnot setříděnou podle velikosti.
Pro dané
hledáme do kterého podintervalu
patří.
Hledání polohy náhodně zadaných bodů
Postupné prohledání nevýhodné - operací (nejhůře), průměrně
Výhodná strategie - půlení intervalu indexů - operací
Postup - Vezmeme index a porovnáme a .
Je-li , pak porovnat a ,
je-li , pak porovnat a .
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 postupně podle velikosti, je výhodné
zahájit hledání v intervalu, kde ležel předchozí bod a pak v sousedních
intervalech.