Today I was having troubles remembering how to code ternary search for integers. Through the ages, people have been taught to divide the interval into three equal length parts. Fortunately Sisu told me that I should not... I believe this is a new thing for some people.
while(lo < hi) {
int mid = (lo + hi) >> 1;
if(f(mid) > f(mid+1)) {
hi = mid;
}
else {
lo = mid+1;
}
}
Have you ever heard about binary search?
You'd normally use binary search for finding an element from an increasing sequence of values, and ternary search for finding the maximum when the values first increase and then start decreasing at some point.
The observation here is that you can replace ternary search with a binary search for the point when the sign between adjacent values change. This is of course a simple thing, but in many places you can find the recommended solution being ternary search, which is harder to get right and less efficient.
Thanks a lot. This comment helped me to understand much more than the whole op post.
Does it work correctly in case f(mid) == f(mid + 1) ?
For example: f = {0, 1, 0, 0, 0}
No, the function should be first strictly increasing and then strictly decreasing or vice versa.
EDIT: increasing/decreasing --> strictly increasing/decreasing
Ok, ternary search also requires strict increase/decrease. So you algorithm is preferable.
Btw, if you search for some "double" answer, there is another intresting way to do that: just divide the segment by golden ratio, for example: AB → ACDB, where C divides AB in the way that AC < CB and D divides AB and AD > DB. The feature is unaware of the sub-segment you choose (AD or CB), one of the points you need on the next step is C or D; it's easy to prove from the definition of golden ratio.
So, you have to calculate only one next func value instead of two, but that can be really important in some cases, for example ones the function I minimized contained Dijkstra algorithm, so that was a cool cheat and my code easily passed TL without optimizing anything else.
Could you please explain the algorithm in more detail? Maybe a sample code will be useful. Thanks in advance.
What you're doing is very similar to binary search on continuous derivative (which may be useful for some floating-point problems, because calculating derivative may be performed with more precision sometimes). If it is below zero until some point and is above zero after that point, then local optima is in the point where derivative is zero. You've calculated discrete derivative and look for a point where it changes the sign.
So, what you are saying is that in some cases you can just use binary instead of ternary? I couldn't understand it well. Would you mind linking me to a problem where this applies?
Thanks in advance!
no, he's not saying that. what he means is that it is sufficient to divide the interval
to 
. this is usually not significant, but it's a reduction nonetheless and may help for problems with tight time limits.
[lo,hi]into two parts, instead of three, while doing ternery search.the benefit is the reduction in complexity from
I don't need to take any special care with the f(mid+1)? If the search goes to the end of the data in my array for example. Actually i just got Accepted with this approach for ternary search by changing it to:
If we look at it from a divide and conquer perspective, you are discarding mid at every iteration, I don't understand how this got accepted.
The safe thing to to do with this approach is to keep a variable which keeps the maximum value of the mid.
If f(mid)>f(mid+1), maybe the mid value found at first iteration is the actual maxima. Now you've reduced search space to [lo,mid-1] regardless. You can just add a line max_val = max(max_val,f(mid)) above it, to make it absolutely correct.
You don't need to worry about mid+1 exceeding high in the author's code, here you've added an extra equal-to lo<**=**high , so you should take care of it.
You're completely right. But it has been such a long time and i don't remember for which problem i have used this code. Thank you.
Hi . I have got a great help from this Blog about Ternary Search . And I have applied in some problems also and got a predicted result . Now My Question is how can I use this Ternary Search for Floating Point Data ??
Thanks in advance .
Click
Thanks for the Problem ... But i want to Know about how can I implement this Code to work out with the double Values in a problem ...
This article of topcoder cookbook can be helpful.
There's a better way: Golden-section search. It reduces hi - lo by a factor of φ ≈ 1.618 by only probing one new point. For example, it can reduce 106 to 1 in around 29 calls to f, instead of 40.
This post is about ternary search on integers. We can't choose integer points in the same way as we do it in golden-section search.
Why not? Just round it to the nearest integer each time.
Yes, the length will be reduced by φ, but the main benefit of this search is that we calculate the function at one point on each iteration after the first. I don't think this property remains if we round the points on each iteration.
You just need to be a bit careful. Here's the code. It calls f up to 31 times.
Nice code, seems I was wrong.
please could you update the code link,its not working
It was a temporary link, the code is now lost forever, sorry about that :(
But it doesn't work for the case f(mid)=f(mid+1)
Ternary search doesn't work either.
Yeah you're right, didn't noticed that, but at least there are some special cases which ternary works, but this doesn't... Doesn't really matter, as I said, I was wrong...
Can you give such special cases? Pretty sure this works as good or better in almost any case.
UPD: Okay apparently it is horrible for problems with real numbers. Example: http://codeforces.me/contest/1059/problem/D But for these problems ternary search is easy to code anyways (because don't have to deal with annoying cases on the integers), so this method really has no drawbacks.
A good problem you can try this on is USACO angry cows (gold). Similar idea to the above problem, but on integers (so you can use this "trick").