CODEWITHSUNDEEP
c++sorting
DreadedSlug
DreadedSlug

Reputation: 583

Divide and conquer algorithm to find position of max element

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; 
}

Upvotes: 5

Views: 2480

Answers (2)

Ahmed Fathy
Ahmed Fathy

Reputation: 1

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;
}

Upvotes: 0

aep
aep

Reputation: 1675

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; 
}

Upvotes: 4

Related Questions