kllp's blog

By kllp, 8 years ago, 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;
}
}  Comments (30)
 » 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}
•  » » 8 years ago, # ^ | ← Rev. 2 →   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 [lo,hi] into two parts, instead of three, while doing ternery search. the benefit is the reduction in complexity from to . this is usually not significant, but it's a reduction nonetheless and may help for problems with tight time limits.
 » 6 years ago, # | ← Rev. 2 →   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: int ternary(int lo, int hi){ while(lo <= hi){ int mid = (lo+hi) >> 1; if(f(mid) > f(mid+1)){ hi = mid-1; } else{ lo = mid+1; } } }
•  » » 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 .
•  » »
•  » » » 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 ...