Divide and conquer algorithm to find position of max element

Question

I am trying to find the index of the max element in an array using a divide and conquer algorithm. Currently, the output is correctly outputting the maximum value of my array, but I cannot figure out how to pass the position of that maximum element.

#include <iostream>

using namespace std;  


int maxElement(int a[], int l, int r) {
   if(r - l == 1) {
        cout << "R - L == 1 " <<  "Array value: " << a[l] << " Pos: " << l << endl;
        return a[l];
   }
   int m = (l + r) / 2;
   int u = maxElement(a, l, m);
   int v = maxElement(a, m, r);
   return u > v ? u : v;    
}

/* Driver program to test above functions */
int main() { 
    int Arr[] = {1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7};
    int arrSize = sizeof(Arr)/sizeof(Arr[0]); 

    cout << maxElement(Arr, 0, arrSize) << endl;
    return 0; 
}

If you know an index, you can get the value in O(1), but if you only know the value, then it takes O(n) (maximum) to iterate through the array and find the index. Have maxElement return an index instead of a value. — JohnFilleau
– JohnFilleau, Commented Feb 20, 2020 at 3:24
Instead of returning a[l] you can return l. And u and v becomes the indexes of max element. You can compare and return a[u]>a[v]?u:v — TruthSeeker
– TruthSeeker, Commented Feb 20, 2020 at 3:28
This is a nice academic excersize, certainly. Unfortunately, it does not really do anything useful or extraordinary. You simply can't get around the fundamental requirement to compare every element in your array. In this case, this is a requirement imposed by some fundamental laws of physics of our shared universe, and the shown code accomplishes that task. But the same will be done, also, by a simple, garden-variety for loop. Nor recursion required. — Sam Varshavchik
– Sam Varshavchik, Commented Feb 20, 2020 at 3:29

aep · Accepted Answer · 2020-02-20 04:05:28Z

4

You can return a std::pair which contains both the array value & position.

#include <iostream>
#include <utility>
using namespace std;  


std::pair<int, int> maxElement(int a[], int l, int r) {
   if(r - l == 1) {
        cout << "R - L == 1 " <<  "Array value: " << a[l] << " Pos: " << l << endl;
        return {a[l], l};
   }
   int m = (l + r) / 2;
   auto up = maxElement(a, l, m);
   auto vp = maxElement(a, m, r);
   return up.first > vp.first ? up : vp;    
}

/* Driver program to test above functions */
int main() { 
    int Arr[] = {1, 4, 9, 3, 4, 9, 5, 6, 9, 3, 7};
    int arrSize = sizeof(Arr)/sizeof(Arr[0]); 
    auto result = maxElement(Arr, 0, arrSize);
    cout << result.first << ", l = " << result.second << endl;
    return 0; 
}

edited Feb 20, 2020 at 4:05

answered Feb 20, 2020 at 3:30

aep

1,73711 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Marek R Over a year ago

question is what if maximum has duplicates? If first maximum should be returned then your fix fails (fix is simple): godbolt.org/z/MbY9EM9M4

Ahmed Fathy · Accepted Answer · 2022-03-23 17:48:32Z

0

You can use this to get the Index of Max Element without using Pair
I hope this will help you

int DAC_Max_Postion(int arr[], int index, int l)
{
    int max;
    if(index >= l - 2)
    {
        if(arr[index] > arr[index + 1])
            return index;
        else
            return index + 1;
    }
    max = DAC_Max(arr, index + 1, l);
    if(arr[index] > arr[max])
        return index;
    else
        return max;
}

answered Mar 23, 2022 at 17:48

Ahmed Fathy

1

Collectives™ on Stack Overflow

Divide and conquer algorithm to find position of max element

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related