random_boi's blog

Ternary search on integer functions where the function is NOT strictly monotonic both ways.
By random_boi, history, 5 years ago, In English

So I know how to do ternary search on a function which is first strictly increasing and then strictly decreasing, but if the function is not strictly increasing but rather non decreasing and then non increasing, is it possible to modify our ternary search to obtain the maximum for such function?

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

Comments Comments (6)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

Think of testcase like this: 1, 1, 1, 1, 1, .... 1, 1, 2, 1, 1, ... 1, 1, 1. We need to find 2, but it is obviously impossible, as we won`t have any additional iformation if we are given the answer that current element value is 2.

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

The problem with the ternary search are the equal numbers. So usually you do it with doubles to avoid collisions.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The actual reason why you see ternary search used in problems that involve functions on reals is that for reasonable functions it's numerically stable. (Small rounding errors when evaluating the function will not produce a large error in the computed result. If you get an incorrect result of comparison due to rounding but your two probes are still far away from each other, it does not matter which third you discard as the maximum is in the middle third anyway.)

    People often use it in discrete settings as well (e.g., find the maximum of an array that increases and then decreases), but in those settings there are better solutions. E.g., you can use binary search on the differences of the array, which is an equal amount of code and finds the maximum in fewer iterations.

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

I guess this blog is what you are looking for.

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

Here's a pretty good solution: Detect sections of uniform values and mark how long they are at each index. Then during the ternary search you can "skip" over these regions by moving the middle values to an edge of the uniform regions.

I don't know how to prove it has the same complexity, but intuitively it's similar.

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

    I don't want to necropost, but how is he going to detect sections of uniform values if he's going to ternary search them? The whole purpose of ternary search is to get an answer in logarithmic time, marking each region would take O(R — L) time.

    → Reply