Today, I was trying to solve 626E - Simple Skewness, and I had some troubles implementing a ternary search on integers! I knew how to run a ternary search on doubles, but I didn't know how to do it on integers.

So after getting it accepted, I tried reading accepted codes of other people and I found a nice way to do it. since many of the best coders in codeforces (including tourist and Errichto) didn't use this while solving 626E - Simple Skewness, I think many people don't know about it!

So here it is!

```
int lo = -1, hi = n;
while (hi - lo > 1){
int mid = (hi + lo)>>1;
if (f(mid) > f(mid + 1))
hi = mid;
else
lo = mid;
}
//lo + 1 is the answer
```

kllp had a blog post about it.

There are also some discussions below.

Correct me if I am wrong but is using the condition r-l < 3 not good enough for ternary search on integers?

ie

//L and R are the range

while(R-L >= 3){

//implementation

}

of course not! both l + 1 and l + 2 can be the answer in this case.

Shouldn't the if condition be

f(mid) > f(mid + 1)?I'm assuming that f[x] increases and then decreases, and we want the maximum value of f[x].

Exactly.

The way it is now, if the condition

f(mid) < f(mid + 1)is fulfilled, you're gonna throw everything in the interval[mid + 1, n]away, since you are setting the higher border as mid; but, the maximumf(i)is in[mid + 1, n]sincef(mid + 1)is greater thanf(mid).Sorry, You're right! I just fixed it.

Thank you so much for this!

I used it to solve this problem

It's very useful :)

You're welcome! It's nice to know that I was helpful :)

Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0}

It's impossible to run ternary search if we allow

f(i) =f(i+ 1).It is still possible if we allow f(i)=f(i+1) only when f(i) is the maximum / minimum we want to find. It's a specific case, but at the same time it's fairly frequent.

Could we check f(mid-1) as well to decide where to go in such a scenario, hoping it isn't the same as f(mid) and f(mid+1).

What if it is? you check f(mid-2)? this might become linear

Just for the sake of example, i would like to put this problem https://mirror.codeforces.com/contest/1426/problem/C , we cannot ternary search it because we have f(i) = f(i+1) even when f(i) is not max or min.

Thanks! I used this trick in 631E - Product Sum and get accepted :)

My code: 16554436

How do you find the convex when i is fixed? There are a lot of local maximum points

I'm RED

How do you run ternary search if f(MID)==f(MID+1) [Or even for that matter what if f((2*LO+HI)/3)==f((LO+2*HI)/3)]??

Look up, man!