CODEWITHSUNDEEP
c++arraysrecursion
RyanJohnTyler
RyanJohnTyler

Reputation: 75

How to find Max in an Array using Recursion and dividing in half?

My professor wants us to use recursion to find a max in an array, specifically by dividing and conquer. By that I mean he wants us to split the array in half, work our way down the bottom half and then through the top half.

However, I'm experiencing several problems with the code. First, I am confused as I'm not sure how to get the array to stop going through the bottom half? I am adding conditional checks to see if it's going through an infinite loop and yet it kinda ignores it. In addition it seems to be going outside the array when it shouldn't be able to in the first place. Then, using the sample code he gives, using flags it seems to skip in a 10 digit array, all the odd numbers.

My code is right here 

#include <iostream>

using namespace std;


int maxarray(const int anarray[], int first, int last)
{
    cout << "call" << endl;
    cin.get();
    int mid = first + (last - first) / 2;
    int firstHalf,lastHalf = 0;
    do{
        cout << firstHalf << " - " << mid << endl;
        cin.get();
    firstHalf = maxarray(anarray, first, mid - 1);
    }
    while(mid!= first);

    do{
    lastHalf = maxarray(anarray, mid+1, last);
    }
    while(mid != last);
    if(firstHalf <= lastHalf)
        return lastHalf;
    else if(lastHalf <= firstHalf)
            return firstHalf;
    else
        return -1;


    }

int main()
{
    int arr[10] = {1,2,3,4,5,6,7,8,9,0};


    for(int x=0;x<10;x++){
        cout << arr[x] << endl;}

    cout << maxarray(arr,0, 10);
}

And using the output I get 

1
2
3
4
5
6
7
8
9
0
call

0 - 5

call

16777216 - 2

call

16777216 - 0

It proceeds into an infinite loop after that last entry. I'm not sure what I'm doing wrong, and googling gets me simple answers but not in the way that he wants me to do it. My textbook just gives me pseudocode that doesn't help either. Conceptually, I understand how I'm supposed to work it but I'm having trouble applying it. I would send him a question but he just forwards me to StackOverflow and other websites for help. enter image description here

Upvotes: 1

Views: 1929

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726629

You are severely overthinking this problem. The process of finding the max recursively by divide-and-conquer strategy is embarrassingly simple:

  • If there's nothing to divide because the range has a single item, return the item
  • Otherwise divide the range in two, call for max on both halves, and return the larger of the two

Here is how it looks in code:

int maxarray(const int a[], int first, int last) {
    // Single-item range
    if (first+1 == last) {
        return a[first];
    }
    // Divide-and-conquer
    int mid = first + (last - first) / 2;
    int leftMax = maxarray(a, first, mid);
    int rightMax = maxarray(a, mid, last);
    return leftMax > rightMax ? leftMax : rightMax;
}

Demo.

Note that despite the fact that we divide the range, the algorithm is still linear, because we solve both sub-problems in all cases. Another way to put it is that we must look at every single item in the range, regardless of the order.

Upvotes: 4

Related Questions