Ternární hledání

Ternární vyhledávání (Ternary search)  je počítačová metoda pro nalezení maxim a minim funkce , která buď nejprve striktně zvyšuje , pak striktně snižuje , nebo naopak. Ternární prohledávání určí, že minimum ani maximum nemůže ležet ani v první, ani v poslední třetině oblasti, a poté zopakuje hledání ve zbývajících dvou třetinách. Ternární vyhledávání demonstruje programovací paradigma „ rozděl a panuj “.

Funkce

Předpokládejme, že hledáme maximum funkce f ( x ), a že víme, že maximum leží mezi A a B . Aby byl algoritmus použitelný, musí existovat nějaká hodnota x taková, že

Algoritmus

/** Najde maximum funkce s jedním extrémem mezi l a r. K nalezení minima stačí prohodit akce ve větvích if/else. */ dvojité l = ..., r = ..., EPS = ...; // vstupní data double m1 , m2 ; while ( r - l > EPS ) { mi = l + ( r - l ) / 3 ; m2 = r- ( r - l ) / 3 ; _ if ( f ( m1 ) < f ( m2 )) l = ml ; jiný r = m2 ; }

Viz také