Ternary Search on Integers!

Правка en2, от Deemo, 2016-02-28 19:15:39

Today, I was trying to solve 626E - Simple Skewness, and I had some troubles implementing a ternary search on integers! I knew how to run a ternary search on doubles, but I didn't know how to do it on integers.

So after getting it accepted, I tried reading accepted codes of other people and I found a nice way to do it. since many of the best coders in codeforces (including tourist and Errichto) didn't use this while solving 626E - Simple Skewness, I think many people don't know about it!

So here it is!

int lo = -1, hi = n;
while (hi — 1 > lo){
    int mid = (hi + lo)>>1;
    if (f(mid) < f(mid + 1)) 
         hi = mid;
    else 
         lo = mid; 
}
//lo + 1 is the answer
Теги tutorial, ternary search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Deemo 2016-02-29 07:51:53 2 Tiny change: 'f (f(mid) < f(mid + 1' -> 'f (f(mid) > f(mid + 1'
en3 Английский Deemo 2016-02-28 19:21:36 14 Tiny change: 'while (hi — 1
en2 Английский Deemo 2016-02-28 19:15:39 4
en1 Английский Deemo 2016-02-28 19:14:32 769 Initial revision (published)