CODEWITHSUNDEEP
algorithmdata-structures
Mr.O
Mr.O

Reputation: 352

Finding maximum in array in time of O(log(n))- with some assumptions

I got the following question: Assume you got an array A with n distinguished numbers, and assume you can store the n-elements in new data structure (one that could help you in solving the question below) while saving the that the store time is bounded by O(n). Write an algorithm for a function max (i,j) which will get as input two index i greater then j , and will return as output the maximum between A[i], A[i+1],...,A[j]. max(i,j) should be bounded by O(log(n)).

I thought about binary tree but could not think about a why of how to store the numbers. One option that I could thought about that take O(n) store time is creating a 'tournament tree' , but I failed to find an algorithm to max using this kind of data structure.

This is a homework question, but couldn't find the tag for it.

Upvotes: 0

Views: 1215

Answers (2)

Shantanu
Shantanu

Reputation: 341

You can solve it using priority queues.

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
int deq[100],length=0;
void increase_value(int arr[],int i,int val)
{
    arr[i]=val;
    while(i>1 && arr[i/2]<arr[i])
    {
        int temp=arr[i];
        arr[i]=arr[i/2];
        arr[i/2]=temp;
        i=i/2;
    }
}
void insert_element(int arr[],int val)
{
    length=length+1;
    increase_value(arr,length,val);
}
int main()
{
    int arr[10000];
    int size,lw,up;
    cin>>size;
    for(int i=1;i<=size;i++)
    {
        cin>>arr[i];
    }
    cin>>lw>>up;
    for(int i=lw;i<=up;i++)
    {
        insert_element(deq,arr[i]);
    }
    cout<<deq[1]<<endl;
}

Upvotes: 0

Kaidul
Kaidul

Reputation: 15915

This is the most typical application of segment tree.

Given an array of number, you can build a segment on top of it with O(n) time complexity and perform query on intervals/ranges in O(logn) time.

Some common application example - finding the sum of elements from index i to j where 0 <= i <= j <= n - 1, finding the maximum/minimum of elements from index i to j where 0 <= i <= j <= n - 1 etc.

Upvotes: 3

Related Questions