How to find the maximum value in any range of an array in log (n) time?

Question

eg. Array: {1, 5, 2, 3, 2, 10}

Range: 0-1 Answer: 5 Range: 2-4 Answer: 3 Range: 0-5 Answer: 10, etc.

Answer 1

If the array is not sorted, then there is no way to do what you are asking for.

To find the maximum, at least you will need to check all the elements in the range that O (n) takes.

If you allow any data preprocessing, this is easy. You can just build n ² lookup table with answers. Then you can find the maximum for any range at a constant time.

Answer 2

It's impossible. You will need to visit each item.

If your array is sorted a-priori, then this is O (1).

Answer 3

See also here: What is the best way to get the minimum or maximum value from an array of numbers?

As others noted that this is not possible

Answer 4

@ Daniel Talamas, if I understood you correctly, you wanted this:

#include <iostream> #include <algorithm> #include <vector> using namespace std; int maxlement(int range1,int range2) { std::vector<int> v{ 1, 5, 2, 3, 2, 10 }; std::vector<int>::iterator result; result = std::max_element(v.begin()+range1, v.begin()+range2+1); int dist = std::distance(v.begin(), result); return v[dist]; } int main() { int range1,range2; cout<<"From "; cin>>range1; cout<<"To "; cin>>range2; cout<<"Max Element Is "<<maxlement(range1,range2); return 0; }