Doubts on Ternary Search

Revision en1, by hello____world, 2020-12-02 19:32:01

I have two doubts regarding Ternary Search, I hope someone can help.

1. Complexity:

In every blog, I find complexty of ternary search as O(log3(N)). I know how we get this complexity but if we do something like this:

int i=0, j=MAX;
while(i<=j){
    int m=(i+j)/2;
    if(eval(m)<eval(m+1)){
        j=m-1;
    }else{
        i=m+1;
    }
}
cout<<j+1;

Wouldn’t complexity be O(log(2))? What are the limitations of this kind of implementation? I believe we can modify this implementation to work with decimal values as well.

2. Type of Function?

Can we use this algorithm work with non-strict decrease-increase function?
If I have a function with values: {5,5,4,3,3,3,2,3,4,4,5} i.e: f(0)=5, f(2)=4 and so on.
How should I implement ternary search on this function?
To be specific, what should I do if f(m1)==f(m2)?

If you have any blog which can help me with these doubts, please share.

Tags ternary search, algorithm complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English hello____world 2020-12-02 19:32:01 981 Initial revision (published)