### hello____world's blog

By hello____world, history, 7 weeks ago,

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.

• +3

 » 7 weeks ago, # |   +8 In complexity all logs with constant base are equal: $\log_b a = \frac{\log a}{\log b}$You can't use it with non-strictly decreasing/increasing functions.
•  » » 7 weeks ago, # ^ |   +8 In complexity all logs with constant base are equal Ah, yes! Thanks.Also is there any problem with using M, M+1 as two points? In almost every tutorial, they divide the array into 3 parts whereas dividing the array into 2 looks like a better solution.
•  » » » 7 weeks ago, # ^ |   +8 Dividing the array into 2 is the integer ternary search, it doesn't work for decimal values. You need to split into 3 for decimal values.
•  » » » » 7 weeks ago, # ^ |   0 Ohkay! Thanks :)
 » 7 weeks ago, # |   +13 Can we use this algorithm work with non-strict decrease-increase function? No. Imagine you have an array that is $1$ everywhere except at one unknown point it is $0$. No matter how you query points, if it evaluates to $1$ every time you cannot guarantee to find the minimum with less than $n-1$ queries.
•  » » 7 weeks ago, # ^ |   0 Got it! Thanks :)