Deemo's blog

Ternary Search on Integers!
By Deemo, history, 9 years ago, In English

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 - lo > 1){
    int mid = (hi + lo)>>1;
    if (f(mid) > f(mid + 1)) 
         hi = mid;
    else 
         lo = mid; 
}
//lo + 1 is the answer
  • Vote: I like it
  • +82
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

kllp had a blog post about it.

There are also some discussions below.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Correct me if I am wrong but is using the condition r-l < 3 not good enough for ternary search on integers?

ie

//L and R are the range

while(R-L >= 3){

//implementation

}

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    of course not! both l + 1 and l + 2 can be the answer in this case.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't the if condition be f(mid) > f(mid + 1)?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm assuming that f[x] increases and then decreases, and we want the maximum value of f[x].

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it -6 Vote: I do not like it

      Exactly.

      The way it is now, if the condition f(mid) < f(mid + 1) is fulfilled, you're gonna throw everything in the interval [mid + 1, n] away, since you are setting the higher border as mid; but, the maximum f(i) is in [mid + 1, n] since f(mid + 1) is greater than f(mid).

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, You're right! I just fixed it.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for this!

I used it to solve this problem

It's very useful :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're welcome! It's nice to know that I was helpful :)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Does it work correctly in case f(mid) == f(mid + 1) ? For example: f = {0, 1, 0, 0, 0}

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    It's impossible to run ternary search if we allow f(i) = f(i + 1).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      It is still possible if we allow f(i)=f(i+1) only when f(i) is the maximum / minimum we want to find. It's a specific case, but at the same time it's fairly frequent.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could we check f(mid-1) as well to decide where to go in such a scenario, hoping it isn't the same as f(mid) and f(mid+1).

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What if it is? you check f(mid-2)? this might become linear

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just for the sake of example, i would like to put this problem https://mirror.codeforces.com/contest/1426/problem/C , we cannot ternary search it because we have f(i) = f(i+1) even when f(i) is not max or min.

      → Reply
»
9 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Thanks! I used this trick in 631E - Product Sum and get accepted :)

My code: 16554436

→ Reply
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

How do you run ternary search if f(MID)==f(MID+1) [Or even for that matter what if f((2*LO+HI)/3)==f((LO+2*HI)/3)]??

→ Reply