random_boi's blog

By random_boi, history, 12 months 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

»
12 months 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.

»
12 months 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.

  • »
    »
    12 months 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.

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't get your idea. If have equal elements, the difference array (derivative) can be 0 at any point. If you hit zero element which side are you going to pick?

»
5 days ago, # |
  Vote: I like it +6 Vote: I do not like it

I guess this blog is what you are looking for.