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

Автор 314rate, история, 6 лет назад, По-английски

Hello!

For finding the minimum with Ternary Search we nead a function that respects this conditions :

for all a,b with A ≤ a < b ≤ x, we have f(a) < f(b), and

for all a,b with x ≤ a < b ≤ B, we have f(a) > f(b).

Is there an algorithm ( also running in logaritmic time ) for finding the minimum in a function like this :

for all a,b with A ≤ a < b ≤ x, we have f(a) <= f(b), and

 for all a,b with x ≤ a < b ≤ B, we have f(a) >= f(b).

Thank You!

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

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

Auto comment: topic has been updated by 314rate (previous revision, new revision, compare).

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

Auto comment: topic has been updated by 314rate (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Short answer: No

Imagine running a ternary search in an array which contains n - 1 zeros and a single 1. Even if you compute f in n - 2 points you cannot be sure about the value of the last two points, given that all the n - 2 points had value 0. This means that, in fact, any search algorithm, and not just ternary search, will have worst case running time Θ(n).