Ternary search with constant ranges

Revision en6, by Al-Merreikh, 2020-02-14 16:54:42

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.

#### History

Revisions

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