La méthode de recherche ternaire est une technique algorithmique utilisée pour trouver l'extremum (minimum ou maximum) d'une fonction unimodale dans un intervalle donné. Elle étend le principe de la recherche binaire en divisant l'intervalle de recherche en trois parties au lieu de deux.

Principe de l'Algorithme

Pour une fonction unimodale (présentant un seul pic ou creux dans l'intervalle), la recherche ternaire fonctionne en réduisant itérativement l'intervalle de recherche. À chaque étape, l'intervalle [l, r] est divisé en trois sous-intervalles. En comparant les valeurs de la fonction aux points de division, on peut éliminer un des trois sous-intervalles, conservant ainsi la portion où l'extremum est susceptible de se trouver.

Étapes de l'Algorithme

1. Division de l'Intervalle : L'intervalle [l, r] est divisé en trois parteis approximativement égales. Les points de division sont généralement calculés comme suit :

• mid1 = l + (r - l) / 3
• mid2 = r - (r - l) / 3

2. Comparaison des Valeurs de la Fonction :

• Si f(mid1) < f(mid2) (dans le cas d'une recherche de maximum), le maximum ne peut pas se trouver dans l'intervalle [l, mid1]. On réduit donc l'intervalle à [mid1, r].
• Si f(mid1) > f(mid2), le maximum ne peut pas se trouver dans l'intervalle [mid2, r]. On réduit donc l'intervalle à [l, mid2].
• Si f(mid1) == f(mid2), le maximum pourrait se trouver entre mid1 et mid2. On réduit alors l'intervalle à [mid1, mid2].

3. Approximatino alternative des points de division : Une autre approche consiste à choisir un point central mid = (l + r) / 2 et à définir deux points très proches de ce centre, par exemple mid1 = mid - eps et mid2 = mid + eps, où eps est une petite valeur. Dans ce cas, l'intervalle est réduit de moitié à chaque itération.

Exemple d'Application

Problème : Recherche du Maximum d'un Polynôme

Soit un polynôme de degré N, garanti d'avoir une forme unimodale sur un intervalle [l, r]. Cela signifie qu'il existe un point x tel que la fonction est croissante sur [l, x] et décroissante sur [x, r]. L'objectif est de trouver ce point x (le maximum).

Format d'Entrée

La première ligne contient un entier N (degré du polynôme) et deux réels l et r délimitant l'intervalle. La seconde ligne contient N+1 coefficients du polynôme, du terme de plus haut degré au terme constant.

Format de Sortie

Un unique réel représentant la valeur de x trouvée. La précision requise est de 10^-5 en erreur absolue ou relative par rapport à la réponse attendue.

Exemple 1

Entrée :

3 -0.9981 0.5
1 -3 -3 1

Sortie :

-0.41421

Explication de l'Exemple

Le polynôme est $f(x) = x^3 - 3x^2 - 3x + 1$. Sur l'intervalle [-0.9981, 0.5], la fonction présente un maximum local autour de $x = -0.41421$. La recherche ternaire permet de converger vers cette valeur.

Implémentation 1 (Division en Tiers)

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

// Utilisation de long double pour une meilleure précision
using ld = long double;
const ld epsilon = 1e-10; // Tolérance pour la convergence

int degree = 0;
std::vector<ld> coeffs;

// Évaluation du polynôme en un point x (méthode de Horner)
ld evaluate_polynomial(ld x) {
    ld result = 0.0;
    for (int i = 0; i <= degree; ++i) {
        result = result * x + coeffs[i];
    }
    return result;
}

// Recherche ternaire
void ternary_search_v1(ld left, ld right) {
    while (right - left > epsilon) {
        ld m1 = left + (right - left) / 3.0;
        ld m2 = right - (right - left) / 3.0;
        
        if (evaluate_polynomial(m1) < evaluate_polynomial(m2)) {
            left = m1; // Le maximum est dans [m1, right]
        } else {
            right = m2; // Le maximum est dans [left, m2]
        }
        // Note: Le cas f(m1) == f(m2) est implicitement géré ici,
        // car on réduira l'intervalle dans tous les cas.
    }
    std::cout << std::fixed << std::setprecision(5) << left << std::endl;
}

int main() {
    ld l_bound, r_bound;
    std::cin >> degree >> l_bound >> r_bound;
    
    coeffs.resize(degree + 1);
    for (int i = 0; i <= degree; ++i) {
        std::cin >> coeffs[i];
    }
    
    ternary_search_v1(l_bound, r_bound);
    
    return 0;
}

Implémentation 2 (Points Proches du Milieu)

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using ld = long double;
const ld point_separation = 1e-10; // Distance entre les points rapprochés

int degree = 0;
std::vector<ld> coeffs;

ld evaluate_polynomial(ld x) {
    ld result = 0.0;
    for (int i = 0; i <= degree; ++i) {
        result = result * x + coeffs[i];
    }
    return result;
}

// Recherche ternaire avec points rapprochés du milieu
void ternary_search_v2(ld left, ld right) {
    while (right - left > point_separation) { // Condition de convergence basée sur l'intervalle
        ld mid = left + (right - left) / 2.0;
        ld point_left = mid - point_separation;
        ld point_right = mid + point_separation;
        
        // S'assurer que les points restent dans l'intervalle [left, right]
        if (point_left < left) point_left = left;
        if (point_right > right) point_right = right;

        if (evaluate_polynomial(point_left) < evaluate_polynomial(point_right)) {
            left = mid; // Le maximum est dans [mid, right]
        } else {
            right = mid; // Le maximum est dans [left, mid]
        }
    }
     std::cout << std::fixed << std::setprecision(5) << left << std::endl;
}

int main() {
    ld l_bound, r_bound;
    std::cin >> degree >> l_bound >> r_bound;
    
    coeffs.resize(degree + 1);
    for (int i = 0; i <= degree; ++i) {
        std::cin >> coeffs[i];
    }
    
    ternary_search_v2(l_bound, r_bound);
    
    return 0;
}

Code Complet Intégré

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using ld = long double;
// Epsilon pour la convergence des deux méthodes
const ld epsilon_v1 = 1e-10; 
// Distance entre les points rapprochés pour la seconde méthode
const ld epsilon_v2 = 1e-10; 

int poly_degree = 0;
ld polynomial_coefficients[20];

// Évaluation du polynôme en x en utilisant la méthode de Horner
ld evaluate(ld x) {
    ld sum = 0.0;
    for (int i = 0; i <= poly_degree; ++i) {
        sum = sum * x + polynomial_coefficients[i];
    }
    return sum; 
}

// Méthode 1 : Division en trois parties égales
void search_ternary_method1(ld l, ld r) {
    while (r - l > epsilon_v1) {
        ld m1 = l + (r - l) / 3.0;
        ld m2 = r - (r - l) / 3.0;
        
        if (evaluate(m1) < evaluate(m2)) {
            l = m1;
        } else if (evaluate(m1) > evaluate(m2)) {
            r = m2;
        } else {
            // Si les valeurs sont égales, on peut réduire des deux côtés
            l = m1;
            r = m2;
        }
    }
    // Affichage final avec la précision requise
    std::cout << std::fixed << std::setprecision(5) << l << std::endl;
}

// Méthode 2 : Points rapprochés du milieu
void search_ternary_method2(ld l, ld r) {
    ld mid_point = 0.0, left_probe = 0.0, right_probe = 0.0;
    // La boucle continue tant que l'intervalle est suffisamment large
    while (r - l > epsilon_v2) { 
        mid_point = (l + r) / 2.0;
        left_probe = mid_point - epsilon_v2; // Point à gauche du milieu
        right_probe = mid_point + epsilon_v2; // Point à droite du milieu

        // S'assurer que les sondes restent dans l'intervalle courant
        if (left_probe < l) left_probe = l;
        if (right_probe > r) right_probe = r;

        // Comparaison pour décider quelle moitié de l'intervalle conserver
        if (evaluate(left_probe) < evaluate(right_probe)) {
            l = mid_point; // Le maximum potentiel est dans la moitié droite
        } else {
            r = mid_point; // Le maximum potentiel est dans la moitié gauche
        }
    }
     // Affichage final avec la précision requise
    std::cout << std::fixed << std::setprecision(5) << l << std::endl;
}

int main() {
    // Optimisation d'entrée/sortie pour C++
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    ld interval_l = 0.0, interval_r = 0.0;
    std::cin >> poly_degree >> interval_l >> interval_r;
    
    for (int i = 0; i <= poly_degree; ++i) {
        std::cin >> polynomial_coefficients[i];
    }
    
    // Appel de la seconde méthode, qui est souvent préférée pour sa simplicité
    search_ternary_method2(interval_l, interval_r);
    
    return 0;
}