Reputation: 31
I learned about ternary search from Wikipedia. I'm not sure what they mean by the parameter absolute precision. They didn't elaborate. But here is the pseudocode:
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)
I want to find max value from a unimodal function. That means I want to print the border point of the increasing and decreasing sequence. If the sequence is
1 2 3 4 5 -1 -2 -3 -4
then I want to print 5 as output.
Here is my attempt. It isn't giving output. Can you please help or give me link that contains good tutorial on ternary search for self learning?
#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);
}
Thank you in advance.
Upvotes: 2
Views: 1669
Reputation: 4871
Absolute precision means the maximum error between the returned result and the true result i.e. max | returned_result - true_result |
. In that context, f
is a continuous function.
Since you are looking at a discrete function, you can't do much better than get to the point where right - left <= 1
. Then, just compare the two resultant values and return the value corresponding to the larger one (since you're looking for max
).
EDIT
The first partition point, being mathematically 2/3*left + right/3
, should be discretized to ceil(2/3*left + right/3)
(so that the relationship is left < first_third <= last_third < right
So first_third = (left*2+right)/3
should be changed to first_third = (left*2 + right + 2)/3
.
Upvotes: 2
Reputation: 148
Try Golden Section search (or Fibonacci search for discrete functions). It has a smaller number of recursions AND a 50% reduction in evaluations of f, compared to the above ternary search.
Upvotes: 0