I'm a CS student and my current assignment is to write a program that will find the largest value in an unsorted array of integers using a recursive divide & conquer algorithm. The concept is straightforward enough, but I'm having trouble with the implementation.

From the diagram I get the idea that you use a helper function to find the larger of two numbers, to determine what to return in the next recursive call. That's simple enough to write. But I don't know how to divide & conquer an array that is unsorted. I'm also not sure what to write for a base case. Can someone help me out here?

## 5 Replies - 12548 Views - Last Post: 20 December 2009 - 08:37 PM

### #1

# Finding the largest value in an unsorted array using recursion

Posted 14 April 2007 - 04:16 PM

##
**Replies To:** Finding the largest value in an unsorted array using recursion

### #2

## Re: Finding the largest value in an unsorted array using recursion

Posted 14 April 2007 - 04:25 PM

i would suggest using a prototype of:

public int largest(int[] array, int current_index, int size_of_array, int max){

these values if incremented properly allow you to traverse the array, and you have a base case of when current_index == size_of_array, then return the max int.

public int largest(int[] array, int current_index, int size_of_array, int max){

these values if incremented properly allow you to traverse the array, and you have a base case of when current_index == size_of_array, then return the max int.

### #3

## Re: Finding the largest value in an unsorted array using recursion

Posted 15 April 2007 - 05:45 AM

This article might help you...

it gives some pseudo-code for quicksort:

http://en.wikipedia.org/wiki/Quicksort

it gives some pseudo-code for quicksort:

http://en.wikipedia.org/wiki/Quicksort

### #4

## Re: Finding the largest value in an unsorted array using recursion

Posted 16 April 2007 - 03:16 PM

Thank you everyone for your input. However I am still stuck. My problem isn't that I am unable to accomplish the task of finding the largest integer in an array. It's doing it the specific way they want me to do it that is giving me fits. I could do it from one end to the other, and retain the max value that would be relatively simple. A recursive version of the bubblesort, as it were. But they want me to specifically divide & conquer, recursively, using a helper function to determine the largest of two values, an unsorted array of integers. I even have the pseudocode I just can't think of any ways to impliment it. Here I'll type the pseudocode for you.

So I understand the concept.. You divide the array in half every recursive call until you are left with essentially all the individual values, which are then compared 2 by 2 using the helper function, each returning the max to the next level above it, until the max value rises to the top. I can describe it, I can tell you the process but I can't DO it for the life of me! lol Maybe I'm just overlooking the painfully obvious (wouldnt be the first time) but can someone please help me figure out how to implement this?

if (anarray has only one item) maxArray(anarray) is the item in anarray else if (anarray has more than one item) maxArray(anarray) is the maximum of maxArray(left half of anarray) and maxArray(right half of anarray)

So I understand the concept.. You divide the array in half every recursive call until you are left with essentially all the individual values, which are then compared 2 by 2 using the helper function, each returning the max to the next level above it, until the max value rises to the top. I can describe it, I can tell you the process but I can't DO it for the life of me! lol Maybe I'm just overlooking the painfully obvious (wouldnt be the first time) but can someone please help me figure out how to implement this?

### #5

## Re: Finding the largest value in an unsorted array using recursion

Posted 20 April 2007 - 03:35 PM

I - finally - did it. I'm so happy. I thought I'd go ahead and post the code here if anyone else has problems like this.

#include <iostream> using std::cout; using std::endl; const int arraysize = 10; int anArray[arraysize] = {100, 12, 89, 17, 33, 7, 97, 2, 4, 105}; int maxArray(int, int, int); int max(int, int); main() { cout << "The largest value in anArray is: " << maxArray(arraysize, 0, (arraysize - 1)) << endl; system("PAUSE"); return 0; } int maxArray(int arraycount, int first, int last) { if (arraycount==1) return max(anArray[first], anArray[last]); else if(arraycount>1) return max(maxArray((arraycount /2), first, (first + last) / 2), maxArray((arraycount /2), (first + last) /2, last)); } max(int x, int y) { if (x > y) { return x; } else { return y; } }

### #6

## Re: Finding the largest value in an unsorted array using recursion

Posted 20 December 2009 - 08:37 PM

You are good at coding

Page 1 of 1