Тернарная поисковая рекурсия неверна

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).

РЕДАКТИРОВАТЬ

ПервоеТочка разбиения, математически 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

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