### Deemo's blog

By Deemo, history, 5 years ago,

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


• +82

 » 5 years ago, # |   +7 zscefn had a blog post about it.There are also some discussions below.
 » 5 years ago, # |   0 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 rangewhile(R-L >= 3){//implementation}
•  » » 5 years ago, # ^ |   +3 of course not! both l + 1 and l + 2 can be the answer in this case.
•  » » » 3 weeks ago, # ^ |   -26 What if we use while (R-L >= 3) { .... } ans = inf; for(i = L; i <= R; i++) ans = min(ans, f(i));
 » 5 years ago, # |   0 Shouldn't the if condition be f(mid) > f(mid + 1)?
•  » » 5 years ago, # ^ |   0 I'm assuming that f[x] increases and then decreases, and we want the maximum value of f[x].
•  » » » 5 years ago, # ^ | ← Rev. 4 →   -6 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 maximum f(i) is in [mid + 1, n] since f(mid + 1) is greater than f(mid).
•  » » » » 5 years ago, # ^ |   0 Sorry, You're right! I just fixed it.
 » 5 years ago, # |   0 Thank you so much for this!I used it to solve this problemIt's very useful :)
•  » » 5 years ago, # ^ |   0 You're welcome! It's nice to know that I was helpful :)
 » 5 years ago, # |   +8 Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0}
•  » » 5 years ago, # ^ |   +59 It's impossible to run ternary search if we allow f(i) = f(i + 1).
•  » » » 5 years ago, # ^ |   +32 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.
•  » » » » 3 years ago, # ^ |   0 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).
•  » » » » » 3 years ago, # ^ |   0 What if it is? you check f(mid-2)? this might become linear
•  » » » 9 days ago, # ^ |   0 Just for the sake of example, i would like to put this problem https://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.
 » 5 years ago, # |   -10 Thanks! I used this trick in 631E - Product Sum and get accepted :)My code: 16554436
•  » » 5 years ago, # ^ |   0 How do you find the convex when i is fixed? There are a lot of local maximum points
•  » » » 5 years ago, # ^ |   0 I'm mambet
 » 3 years ago, # |   -17 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)]??
•  » » 3 years ago, # ^ |   0 Look up, man!