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

Question

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.

Hint: Keep splitting the array until you only have two values. Compare those and return the largest — NathanOliver
– NathanOliver, Commented Apr 11, 2018 at 16:59

Sergey Kalinichenko · Accepted Answer · 2018-04-11 17:07:17Z

4

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.

answered Apr 11, 2018 at 17:07

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

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

1 Comment

RyanJohnTyler Over a year ago

Thank you, this fixed it entirely. I was overthinking it hardcore

Collectives™ on Stack Overflow

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

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related