Căutare ternară

Căutarea ternară (Ternary search)  este o metodă informatică pentru găsirea maximelor și minimelor unei funcții care fie mai întâi crește strict , apoi scade strict sau invers. Căutarea ternară determină că minimul sau maximul nu se poate afla nici în prima sau în ultima treime a regiunii, apoi repetă căutarea pe celelalte două treimi rămase. Căutarea ternară demonstrează paradigma de programare „ împărțiți și cuceriți ”.

Funcția

Să presupunem că căutăm maximul funcției f ( x ) și că știm că maximul se află între A și B . Pentru ca algoritmul să fie aplicabil, trebuie să existe o valoare a lui x astfel încât

Algoritm

/** Găsește maximul unei funcții cu un extremum între l și r. Pentru a găsi minimul, este suficient să schimbați acțiunile din ramurile if/else. */ dublu l = ..., r = ..., EPS = ...; // date de intrare dublu m1 , m2 ; în timp ce ( r - l > EPS ) { m1 = l + ( r - l ) / 3 ; m2 = r - ( r - l ) / 3 ; dacă ( f ( m1 ) < f ( m2 )) l = m1 ; altfel r = m2 ; }

Vezi și