My ternary search recursion isn't correct..it's not giving any output

[prodhan]

I learned about ternary search from wikipedia. I am not sure what they mean by the parameter absolute precision.They didn't elaborate. but here is there 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 unidomal 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 attemp. It isn't giving any output..Can u pls help?or will pls kindly 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);
}

I tried another attempt where I compared last two points and tried to print the maximum element but in vain. Same problem,no output.

Thank you in advance.

[kbw]

Have you thought about what if(right-left<precval) means with int precval=1;?

[prodhan]

yes, I have already fixed that.. But still that isn't working..
I edited it writing if(right-left<=precval)

[kbw]

I'd go for changing the precision of the search rather than doing that. Anyway, have you stepped thru it with a debugger? If you don't have one, trace statements will do. Debugging is a part of programming.

[prodhan]

I don't have a debugger..I worked by hand for simple input..It works there.Can u provide me with a name of a good debugger?

[filipe]

MS VC++ Express has an excellent debugger.

[prodhan]

I've solved it..For ur convenience, I'm sharing what was wrong with this code:

In ternary search when there are <=3 values left you have to handle it in base case. Otherwise it may cause stack overflow because function with same parameter is called again and again.[Remember in binary search base case is when <=2 values are left]

Example: N = 3
values are 0 2 1
first call-> ternary_search(arr, 0, 2)
first_third = 0 // observe left and first_third has become same, so you have to handle this as a base case i.e. right-left<=2 is base case.
second_third = 1

arr[first_third] < arr[second_third]

So you again call ternary_search(arr, 0, 2)
Dat was the problem.. :)