Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Captain_Knuckles's blog

By Captain_Knuckles, history, 12 days ago, In English,

Hi codeforces

Today i will talk about special case in Ternary search

You know when we use Ternary search it's done on a parabola to find its peak

This is a simple code to find the peak of a parabola where the peak is facing down :

L = range_beginning, R = range_ending;

while(R > L) {
    x = (L+R)/2; 
    if( f(x+1) < f(x) )
        L = x+1;
    else
        R = x;
}

But in this special case i need to find the peak of a parabola that has constant value in some ranges as shown on the photo below :

You notice that f(x) = f(x+1) therefor the code from above won't work correctly in this case.

I need help to find a solution for that case.

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by Captain_Knuckles (previous revision, new revision, compare).

»
12 days ago, # |
  Vote: I like it +34 Vote: I do not like it

Unless you know something more about this function, this seems quite impossible. Imagine a function that is constant almost everywhere, apart from some tiny interval $$$[l, r]$$$ where it's a convex parabola. For example:

$$$ f(x) = \begin{cases} (x-4.2)^2 - 0.001^2 & \text{if } |x - 4.2| \le 0.001, \\ 0 & \text {otherwise.} \end{cases} $$$

Until you query for a point in that very tiny interval, you won't be able to find the peak (using any algorithm!). If this interval is very small compared to the domain of the function, you'll unfortunately be unable to find the minimum.