Коррекция тернарных поисков неверна

Question

Я узнал о тройном поиске из Википедии. Я не уверен, что они подразумевают под абсолютной точностью параметра. Они не уточнили. Но вот псевдокод:

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) 

Я хочу найти максимальное значение из унимодальной функции. Это означает, что я хочу напечатать граничную точку возрастающей и уменьшающейся последовательности. Если последовательность

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

тогда я хочу напечатать 5 как выход.

Вот моя попытка. Это не дает выход. Не могли бы вы помочь или дать мне ссылку, содержащую хороший учебник по тройному поиску самостоятельного обучения?

#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); 
} 

Заранее спасибо.

Answer 1

Абсолютная точность означает максимальную ошибку между возвращенным результатом и истинным результатом, то есть max | returned_result - true_result |. В этом контексте f является непрерывной функцией.

Поскольку вы смотрите на дискретную функцию, вы не можете сделать намного лучше, чем добраться до точки, где right - left <= 1. Затем просто сравните два результирующих значения и верните значение, соответствующее большему (поскольку вы ищете max).

EDIT

Первая точка раздела, будучи математически 2/3*left + right/3, следует дискрети- в ceil(2/3*left + right/3) (так что отношения left < first_third <= last_third < right

Так first_third = (left*2+right)/3 должен быть изменен на first_third = (left*2 + right + 2)/3.

Answer 2

Попробуйте Golden Поиск разделов (или поиск по Фибоначчи для дискретных функций). Он имеет меньшее количество рекурсий и 50% -ное снижение оценки по сравнению с предыдущим тройным поиском.