Ternary search with constant ranges
Difference between en2 and en3, changed 6 character(s)
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 : ↵

![ ](/predownloaded/ce/ee/ceee97367c07bea39ace6a69d8e9154e866532b7.png)↵

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.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Al-Merreikh 2020-02-14 16:54:42 10
en5 English Al-Merreikh 2020-02-14 16:52:17 7
en4 English Al-Merreikh 2020-02-14 16:51:39 20
en3 English Al-Merreikh 2020-02-14 16:47:46 6 (published)
en2 English Al-Merreikh 2020-02-14 16:46:09 14 (saved to drafts)
en1 English Al-Merreikh 2020-02-14 16:45:02 787 Initial revision (published)