Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Divide and conquer algorithms to find the maximum element of an array

Tags:

c++

arrays

I am trying to understand how the following algorithms works.

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

First, what I am interested in is that in spite of algorithm's working correctly, it is mysterious for me how it finds the maximum element. I will show how I understood this algorithm:

Step 1: we say that in case of an array, l=0 and r=10, it checks if (l>r) which does not hold of course so it calculates m=(0+10)/2;. Then do again the procedure for new bounds. The first pair is (0,5), the second is (6,10) and after the final operation it compares two returned values and finally returns the maximum element between them.

Does this algorithm always work? In each iteration it does not do any comparison, only the final step. How can it determine the maximum element at each recursive iteration? It checks only what. For example: take pair(0,5), is (0 more than 5)? No, so repeat again and divide these bounds into two so get new average value m1=(0+5)/2 then again again and return some element but not the maximum. Also for second subarray we can say the same.

What is the main idea of this algorithm?

like image 708
dato datuashvili Avatar asked Sep 06 '11 12:09

dato datuashvili


People also ask

How do you find the maximum element in an array using divide and conquer?

Divide and Conquer : Tournament Method Just like the merge sort, we could divide the array into two equal parts and recursively find the maximum and minimum of those parts. After this, compare the maximum and minimum of those parts to get the maximum and minimum of the whole array.

How do you find the maximum element of an array?

Initialize max with the first element initially, to start the comparison. Then traverse the given array from second element till end, and for each element: Compare the current element with max. If the current element is greater than max, then replace the value of max with the current element.


1 Answers

Your confusion is understandable: the algorithm as written contains a couple of bugs. It accesses memory past the end of a, which is very, very bad. Also, the test whether a range contains only one element is incorrect. If not addressed, this leads to a stack overflow.

The way the maximum function is called suggests that the lower bound is included in the range, but the upper bound is not. a[0] is valid, but a[n] accesses memory past the end of a. When splitting the range, we want the first part to run from l up to but not including m, and the second part to start at m and run up to but not include r. In other words: the "exclusive" upper limit of the first part is equal to the "inclusive" lower limit of the second part. The first internal call to maxsimum is correct. The second internal call should be:

int v=maxsimum(a,m,r); 

This leaves us with the problem of detecting a range of length 1. As it stands, the algorithm actually looks for an empty range. The proper test is to look at the difference between the upper and the lower bound:

if (r-l == 1) return a[l];

The complete function is as follows:

int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

Now that we have a correct program, the explanation of how this works is straightforward:

  1. If the range contains only one element, then this element is the maximum.
  2. If the range contains more than one element, we split it in two parts. We call the function recursively to compute the maximum of each part. The maximum of these two values is the maximum of the entire range.
like image 73
Jeffrey Sax Avatar answered Sep 21 '22 01:09

Jeffrey Sax