Recursively find min and max value in array

Question

I made a recursive function to find the max and min value from an array which may contain arbitrary number of elements. The main reason behind making this was to develop an idea in finding the min max value from the pixel data of a Dicom image. I made this recursive function as a test code where I filled an int type array with random numbers ranging from 0-1000. My code is as below. I presented the whole code, you can run the program very easily in Visual Studio yourself.

#include <stdio.h>
#include <string>
#include <iostream>
#include <math.h>
#include <time.h>
using  namespace std;

void recursMax(int* a, int size, int* maxValue)
{
    int half = size/2;
    int* newMax = new int[half];
    for(int i=0; i<half; i++)
    {
        newMax[i]=a[i]>a[size-i-1]?a[i]:a[size-i-1];
    }
    if(half>1)
    {
        recursMax(newMax, half, maxValue);
    }
    if(half == 1)
    {
        *maxValue = newMax[0];
        delete [] newMax;
    }
}

void recursMin(int* a, int size, int* minValue)
{
    int half = size/2;
    int* newMin = new int[half];
    for(int i=0; i<half; i++)
    {
        newMin[i]=a[i]<a[size-i-1]?a[i]:a[size-i-1];
    }

    if(half>1)
    {
        recursMin(newMin, half, minValue);
    }
    if(half == 1)
    {
        *minValue = newMin[0];
        delete [] newMin;
    }
}

int main ()
{
    int size = 100;
    int* a = new int[size];
    srand(time(NULL));
    for(int i=0; i<size; i++)
    {
        a[i]=rand()%1000;
        cout<<"Index : "<<i+1<<",  "<<a[i]<<endl;
    }
    cout<<endl<<endl<<"Now we look to find the max!"<<endl;
    int maxValue = 0;
    int minValue = 0;
    recursMax(a, size, &maxValue);
    cout<<maxValue<<endl;
    recursMin(a, size, &minValue);
    cout<<"Now we look for the min value!"<<endl<<minValue<<endl;
    cout<<"Checking the accuracy! First for Max value!"<<endl;
    for(int i=0; i<size; i++)
    {
        cout<<"Index : "<<i+1<<",  "<<maxValue-a[i]<<endl;
    }
    cout<<"Checking the accuracy! Now for min value!"<<endl;
    for(int i=0; i<size; i++)
    {
        cout<<"Index : "<<i+1<<",  "<<a[i]-minValue<<endl;
    }
    delete [] a;
    return 0;
}

My question to you is that, do you think my algorithm works correctly? I'm have some doubt. Also, am I handling or maintaining the memory correctly? Or there will be some memory leakage in the code?

If half is never equal 1, then you could leak newMin array. Since you are dividing by 2, it may be possible that it never reaches 1. Plus it seems like you are allocating over and over every time recursMax is called. So that when it is unrolled, that delete[] may not be hit. Same thing for recursMin. — user2591612
– user2591612, Commented Mar 20, 2014 at 11:56
allocating memory just to find the minimum in an array is a quite bad idea. Why not simply loop over the array and to find the minimum? — gexicide
– gexicide, Commented Mar 20, 2014 at 11:58
@GIJoe Half does equals to 1 at the final stage! I checked it! — the_naive
– the_naive, Commented Mar 20, 2014 at 11:58
Recursion really isn't the best way to implement this in C++. You expose yourself to the the chance of running out of stack space when processing a large array, so you should go with a procedural approach. — Sean
– Sean, Commented Mar 20, 2014 at 12:12

Ryzhehvost · Accepted Answer · 2014-03-20 12:11:48Z

2

You should take delete [] newMax; out of last if statement, otherwise you'll never free memory. Like this:

if(half == 1)
{
    *maxValue = newMax[0];
}
delete [] newMax;

And the same for recursMin function.

Your algorithm seems working, but excessive. Using recursion and allocating memory just to find min and max is not a good style.

answered Mar 20, 2014 at 12:11

Ryzhehvost

3951 silver badge9 bronze badges

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

1 Comment

the_naive Over a year ago

I wanted to do that, but I feared that delete [] newMax; may lead to heap error. Apparently there's no heap error, I changed the code, and it seems working fine.

Sean · Accepted Answer · 2014-03-20 12:19:43Z

1

For the max value I'd go with something like this:

int ArrayMax(const int *begin, const int *end)
{
  int maxSoFar = *begin;  // Assume there's at least one item

  ++begin;

  for(const int *it = begin; it!=end; ++it)
  {
    maxSoFar = std::max(maxSoFar, *it);
  }

  return maxSoFar
}

Now you can say:

int main ()
{
  int size = 100;
  int* a = new int[size];
  srand(time(NULL));
  for(int i=0; i<size; i++)
  {
    a[i]=rand()%1000;
    cout<<"Index : "<<i+1<<",  "<<a[i]<<endl;
  }

  int theMax = ArrayMax(a, a+size);
}

Needless to say, you can convert ArrayMax into a template function to take any type, and ArrayMin is easily implemented using the same pattern.

answered Mar 20, 2014 at 12:19

Sean

62.8k11 gold badges101 silver badges138 bronze badges

1 Comment

the_naive Over a year ago

Thanks for the answer! My mistake was that I didn't know stdhas a max function! But of all the suggested approach I like it the most!

user1767754 · Accepted Answer · 2017-03-29 08:56:26Z

1

I would suggest this code for finding the minimum, maximum is similar:

int min = std::numeric_limits<int>::max();
for(int i = 0; i < size ; i++) min = std::min(min,a[i]);

A lot shorter, no memory allocation, easy loop so the compiler will probably 1) vectorize it for maximum speed 2) use correct prefetching for even higher speed.

edited Mar 29, 2017 at 8:56

user1767754

25.6k21 gold badges167 silver badges177 bronze badges

answered Mar 20, 2014 at 12:02

gexicide

40.5k26 gold badges104 silver badges166 bronze badges

4 Comments

the_naive Over a year ago

The first line gives the error a value of type "int (__cdecl *)()" cannot be used to initialize an entity of type "int".

the_naive Over a year ago

The first line should be int min = std::numerical_limits<int>::max();. Thanks anyways.

the_naive Over a year ago

Nice answer, but not quite accurate! Instead of int min = std::numerical_limits<int>::max;, we should do int min = a[0]. Otherwise the min will the be min value of int type.

gexicide Over a year ago

@the_naive: a[0] is fine as well, but max is fine too. Please regard that I use max, not min!

Jarod42 · Accepted Answer · 2014-03-20 13:38:19Z

0

Using algorithm from STL:

Since C++11: you may use std::minmax_element to retrieve both at once : https://ideone.com/rjFlZi

const int a[] = {0, 1, 42, -1, 4};

auto it = std::minmax_element(std::begin(a), std::end(a));
std::cout << *it.first << " " << *it.second << std::endl;

In C++03, you may use std::min_element and std::max_element.

answered Mar 20, 2014 at 13:38

Jarod42

228k15 gold badges214 silver badges351 bronze badges

Comments

4pie0 · Accepted Answer · 2014-03-27 23:32:05Z

This is terrible algorithm for finding minimum and maximum. You can use simpler, shorter and faster solution:

const int maxInArray( const int* beg, const int* end) {
const int* it  = std::max_element( beg, end);
    if ( it == end)
    {
        std::cout << "There is no smallest element" << std::endl;
    }
    else
    {
        std::cout << "The smallest element is " << *it << std::endl;
    }
return *it;
}

or iterate over the array:

int maxInArray( const int* beg, const int* end) {
    int max;
    if ( end - beg < 1 ) return -1;
    max = *beg
    while ( beg++ != end) {
        if ( *beg > max) max = *beg;
    }
    return max;
}

with no boost support:

#include <iostream>
#include <limits>

int main() {
    int max = std::numeric_limits<int>::min();
    int min = std::numeric_limits<int>::max();
    int num;

    while ( std::cin >> num) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
    }
    std::cout << "min: " << min << std::endl;
    std::cout << "max: " << max << std::endl;

    return 0;
}

or with help from boost:

#include <iostream>
#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics/stats.hpp>
#include <boost/accumulators/statistics/min.hpp>
#include <boost/accumulators/statistics/max.hpp>
using namespace boost::accumulators;


int main() {
    // Define an accumulator set for calculating the mean, max, and min
    accumulator_set<double, features<tag::min, tag::max> > acc;

    int num = -1;
    bool empty = true;

    while ( std::cin >> num && num >= 0) {
        empty = false;
        acc( num);
    }

    if ( ! empty) {
        // Display the results ...
        std::cout << "Min: " << min( acc) << std::endl;
        std::cout << "Max: " << max( acc) << std::endl;  
    }

    return 0;
}

Rajveer Sidhu · Accepted Answer · 2016-02-22 00:24:40Z

-1

Basically finding max in array is not recommended by recursion as it is not required. Divide and conquer algorithms(recursive) are more time costly. But even though if you want to use it, you can use my below algorithm. Basically, it brings the largest element of array at first position and has almost linear running time.(This algo is just a recursive-illusion though!):

    int getRecursiveMax(int arr[], int size){
      if(size==1){
                  return arr[0];
      }else{
             if(arr[0]< arr[size-1]){
                                  arr[0]=arr[size-1];
                 }
             return(getRecursiveMax(arr,size-1));
        }

      }

answered Feb 22, 2016 at 0:24

Rajveer Sidhu

52 bronze badges

2 Comments

Andy Over a year ago

Please don't simply copy and paste your answer to multiple questions. Ensure that your post answers the question being asked and you aren't simply pasting your answer in multiple places without actually answering the question.

Rajveer Sidhu Over a year ago

Hi Andy, Thanks for the suggestion! :-) But I just wrote this to answer this question too. There can be two functions getRecursiveMax() and getRecursiveMin(). One has to replace > sign with < and one can find max and min both. I didnt write the other function as I think its understood.

Collectives™ on Stack Overflow

Recursively find min and max value in array

6 Answers 6

1 Comment

1 Comment

4 Comments

Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

1 Comment

4 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related