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

How to find the maximum element of an unsorted array in O(log n)?
Автор Closed_, история, 3 года назад, По-английски

Hi everyone!

Does there an algorithm find the maximum element of an unsorted array in o(log n), and what about a bitonic array? I searched for this but have not found any solution to this problem!

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

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

Check out cp-algorithms.com. You should be able to find your answers there. Segment tree will do.

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

Without any more information, the answer is no.

But you can use data structure suchs as segment tree, rmq, casterian tree, ... to find max-min on a segment in $$$O(log n)$$$

→ Ответить