La récursivité de recherche ternaire n'est pas correcte

Question

J'ai découvert la recherche ternaire de Wikipedia. Je ne suis pas sûr de ce qu'ils veulent dire par le paramètre de précision absolue. Ils n'ont pas élaboré. Mais voici le pseudo-code:

def ternarySearch(f, left, right, absolutePrecision): 
    #left and right are the current bounds; the maximum is between them 
    if (right - left) < absolutePrecision: 
     return (left + right)/2 

    leftThird = (2*left + right)/3 
    rightThird = (left + 2*right)/3 

    if f(leftThird) < f(rightThird): 
     return ternarySearch(f, leftThird, right, absolutePrecision) 

    return ternarySearch(f, left, rightThird, absolutePrecision) 

Je souhaite trouver la valeur maximale d'une fonction unimodale. Cela signifie que je veux imprimer le point de bordure de la séquence croissante et décroissante. Si la séquence est

1 2 3 4 5 -1 -2 -3 -4 

alors je veux imprimer 5 en sortie.

Voici ma tentative. Il ne donne pas de sortie. Pouvez-vous s'il vous plaît aider ou me donner un lien qui contient un bon tutoriel sur la recherche ternaire pour l'auto-apprentissage?

#include<iostream> 

using namespace std; 
int ternary_search(int[], int, int, int); 
int precval = 1; 

int main() 
{ 
    int n, arr[100], target; 
    cout << "\t\t\tTernary Search\n\n" << endl; 
    //cout << "This program will find max element in an unidomal array." << endl; 
    cout << "How many integers: "; 
    cin >> n; 
    for (int i=0; i<n; i++) 
     cin >> arr[i]; 
    cout << endl << "The max number in the array is: "; 
    int res = ternary_search(arr,0,n-1,precval)+0; 
    cout << res << endl; 
    return 0; 
} 

int ternary_search(int arr[], int left, int right, int precval) 
{ 
    if (right-left <= precval) 
     return (arr[right] > arr[left]) ? arr[right] : arr[left]; 
    int first_third = (left * 2 + right)/3; 
    int last_third = (left + right * 2)/3; 
    if(arr[first_third] < arr[last_third]) 
     return ternary_search(arr, first_third, right, precval); 
    else 
     return ternary_search(arr, left, last_third, precval); 
} 

Merci d'avance.

Answer 1

Une précision absolue signifie l'erreur maximale entre le résultat renvoyé et le résultat vrai, c'est-à-dire max | returned_result - true_result |. Dans ce contexte, f est une fonction continue.

Puisque vous regardez une fonction discrète, vous ne pouvez pas faire beaucoup mieux que d'arriver au point right - left <= 1. Ensuite, comparez simplement les deux valeurs résultantes et renvoyez la valeur correspondant à la plus grande (puisque vous recherchez max).

EDIT

Le premier point de la partition, étant mathématiquement 2/3*left + right/3, devrait être discrétisée à ceil(2/3*left + right/3) (de sorte que la relation est left < first_third <= last_third < right

Alors first_third = (left*2+right)/3 devrait être remplacé first_third = (left*2 + right + 2)/3.

Answer 2

Essayez d'or Recherche de section (ou recherche de Fibonacci pour des fonctions discrètes) Il a un plus petit nombre de récursions et une réduction de 50% ons de f, par rapport à la recherche ternaire ci-dessus.