Блог пользователя random_boi

Ternary search on integer functions where the function is NOT strictly monotonic both ways.
Автор random_boi, история, 6 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I guess this blog is what you are looking for.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    → Ответить