PROGRAMMING PROBLEMS 2.4.3 Finding the Largest Value in an Array Suppose that yo

Question

PROGRAMMING PROBLEMS

2.4.3 Finding the Largest Value in an Array Suppose that you have an array anArray ofintegers and you want to find the largest value. You could construct an iterative solution without too much difficulty, but instead let's consider a recursive for mulation if an has only one entry max Array CanArray is the entry in anArray else if CanArray has more than one entry max Array CanArray) is the maximum o max left half of anAr and maxArray Cright half of anArray) Notice that this strategy fitsthedivide-and-conquer model that the previous binary search algorithm used. That is, we proceed by dividing the problem and conquering the subproblems, as Figure 2-12 illustrates. However, there is a difference between this algorithm and the binary search algorithm. Although the binary search algorithm conquers only one of its subproblems at each step, maxArray conquers both. Because both subproblems are solved recursively, this approach is called multipath recursion. After maxArray conquers the subproblems, it must reconcile the two solutions that is, it must find the maximum of the two maximums. Figure 2-13 illustrates the computations that are neces- sary to find the largest integer inthe array that contains l, 6, 8, and 3 (denoted hereby 1,6,8,3 Question 7Define the recursive C++ function maxArray that returns the largest value in an array and adheres to the pseudocodejust given 2.4.4 Finding the kth Smallest Value of an Array Our discussion of searching concludes with a more difficult problem. Although you could skip this example now, Chapter 11 uses aspects ofit in a sorting algorithm.

Explanation / Answer

Below is the recursive program with comments inline

int findLargestValue(int arr[], int left, int right)

{

//if array has only one entry, maxarray is that entry

if (right - left == 1)

return arr[left];

//calculate the middle point

int midPoint = (left + right) / 2;

//lets find largest from the left half of the array recursively

int largestInLeftArray = findLargestValue(arr, left, midPoint);

//lets find largest from the right half of the array recursively

int largestInRightArray = findLargestValue(arr, midPoint, right);

//return the largest amongst both the arrays

return largestInLeftArray > largestInRightArray ? largestInLeftArray : largestInRightArray;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.