Closed_'s blog

How to find the maximum element of an unsorted array in O(log n)?
By Closed_, history, 3 years ago, In English

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!

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

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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)$$$

→ Reply