Finding minimum number using maximum range query

Revision en1, by kingofnumbers, 2015-07-01 18:14:45


I have a question that come to my mind but I'm not able to solve it:

Given N , you know there's an array of N integers but you don't know integers of the array , you only know N.

you want to find minimum integer of this array, in order to do that you can ask questions of form: L R

it means what's the maximum number among all integers from index L to R (inclusive)

you will know the index and the value of the maximum integer

in case we can ask O(N) questions then we can query every integer alone and get the minimum one

but is there's any way to know the minimum integer of this array using less than O(N) questions ?

if there's no way how to prove that formally?


  Rev. Lang. By When Δ Comment
en1 English kingofnumbers 2015-07-01 18:14:45 746 Initial revision (published)