Table of Contents
Divide and Conquer is a style of recursive algorithm where the problem set at each step gets split into parts, then the function recurses with those smaller parts, until the terminating case where - for example - there's only one "part" to solve and a solution can be found.
For example, with MergeSort, we would break each set in half and then call the recursive MergeSort function twice - once for the left half and once for the right half. As a result of the recursion, the left half is then cut into halves and MergeSort are called on those halves, and so on and so forth until the subset is just 1 item, which is inherently sorted.
// One of the functions for MergeSort template <typename T> void MergeSort_Recursive( vector<T>& arr, size_t left, size_t right ) { if ( left < right ) { size_t mid = ( left + right ) / 2; MergeSort_Recursive( arr, left, mid ); MergeSort_Recursive( arr, mid+1, right ); MergeEm( arr, left, mid, right ); } }
1. Divide and conquer: Find the max value in an array
Let's say we have an array and want to find the maximum value stored within:
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| A | D | B | C |
You are able to solve this iteratively with a loop, but let's break
it down in a divide-and-conquer manner. Like with MergeSort, when
FindMax( { 'A', 'D', 'B', 'C' } ) is called, it will split that
array in half, recursing for both halves, then those halves will
be broken down further, until only one element is in the array:
FindMax( { 'A', 'D', 'B', 'C' } )FindMax( { 'A', 'D' } )FindMax( { 'A' } )FindMax( { 'D' } )
FindMax( { 'B', 'C' })FindMax( { 'B' } )FindMax( { 'C' } )
Our terminating case will be when the array only has one item: If there's only one item, then that one item is the max.
FindMax( { 'A', 'D', 'B', 'C' } )FindMax( { 'A', 'D' } )FindMax( { 'A' } )= 'A'FindMax( { 'D' } )= 'D'
FindMax( { 'B', 'C' })FindMax( { 'B' } )= 'B'FindMax( { 'C' } )= 'C'
At the next level, say FindMax( { 'A', 'D' } ), it now has two
items returned; let's say "left" and "right"…
// (Pseudocode)
left = FindMax( { 'A' } )
right = FindMax( { 'D' } )
Then we have to decide which of these two returned values is the maximum:
// (Pseudocode) if ( left > right ) return left else return right
So then FindMax( { 'A', 'D' } ) will look at 'A' and 'D' and then
return 'D' as its result.
FindMax( { 'A', 'D', 'B', 'C' } )FindMax( { 'A', 'D' } )= 'D'FindMax( { 'B', 'C' } )= 'C'
This would then continue repeating until we got to the original
call to the FindMax function, returning the final result.
Splitting vectors in C++ is kind of a pain in the butt, so another
way we can look at this is to use indices i and j and finding
the center-point mid and splitting these up in that way…
FindMax( { 'A', 'D', 'B', 'C' }, 0, 3 )– investigate entire arrayFindMax( { 'A', D', 'B', 'C' }, 0, 1 )– look at 0 and 1FindMax( { 'A', D', 'B', 'C' }, 0, 0 )– look at 0FindMax( { 'A', D', 'B', 'C' }, 1, 1 )– look at 1
FindMax( { 'A', D', 'B', 'C' }, 2, 3 )– look at 2 and 3FindMax( { 'A', D', 'B', 'C' }, 2, 2 )– look at 2FindMax( { 'A', D', 'B', 'C' }, 3, 3 )– look at 3
It's perhaps less visually clear than the previous example, but the index values provided denote the left and right regions to investigate.
char maxLeft = FindMax_Recursive( i, mid, letters ); char maxRight = FindMax_Recursive( mid+1, j, letters );
Then the logic to check if left or right is bigger would be the same.