Divide and Conquer: The Art of Breaking Down Problems | Recursion Series

foreign hey guys welcome back this is William today I want to start talking about the divide and conquer Paradigm we often see in recursive programming divide and conquer is a way to simplify a problem by breaking it down into smaller more manageable sub problems it is based on the idea that solving these smaller subproblems independently and then combining their Solutions can lead to the overall solution of the original problem it's a technique that we see used all over the recursion landscape including sorting algorithms like merge sort and quick sort in the search algorithm space like binary search and in many other algorithmic problems that exhibit overlapping sub problems in the last video we looked at how to find the maximum element and its index by iterating through a list recursively checking each element one at a time while this certainly is one way of solving problems recursively it's not very different from a traditional Loop structure if you think about it today

we're going to begin looking at a more interesting way of solving these recursive Problems by using Divine conquer paradigm let's rethink of how we can solve finding the maximum element in a list instead of going through the array left to right like we did previously instead of we're going to be breaking this problem down to smaller and simpler sub problems recall that our original goal is to find the maximum number in a list notice that if we split the array into a left and a right component that finding the maximum of the left and the right array equals the maximum of the whole array this is important to note because it means that splitting up the array to find the maximum will not change the value of the true maximum of the whole array after we split the original list into two parts we can further split the lists again into four lists and then split those four lists into eight lists composed of individual elements now going back to the original problem we're trying to solve which is finding the maximum element we know we can combine two lists of numbers together to find the maximum of those two lists we also trivially know that the maximum element in a list with a single value is the value itself with this information we can begin finding the maximum value of the entire list by working our way upwards let's begin in combining lists together on the lower left starting with two and one the max of two and one is two so we can return to as the maximum value then it would take the max of 0 and negative four which is zero then the max of 3 and 6. and 7 and 5. after that we can reapply the same process to the third row the max of 2 and 0 is 2. so we place two as the maximum value for that sub list and then the max of six and seven is seven so seven becomes the max value of the right sub list then we reapply the same process for the final two sub lists the max of two and seven is seven and in the N7 is the maximum element in the list this process that we just saw breaking down a problem into simpler sub problems and then solving those sub-problems is what we call divide and conquer

awesome now let's take a glance at how the Divine conquer algorithm for finding the maximum element is implemented you'll see that we're repeatingly splitting the current segment based on the interval from I to J at some midpoint however before we run through this code in detail I want to illustrate how the division of the segments takes place because it might not be so obvious let's imagine we have a given list and our objective is to divide it into smaller lists to accomplish this we maintain a record of the indices representing the segments of the list as we progress down the tree this approach enables us to keep track of the specific portions of the list that we're working on eliminating the need to create a copy of the segment itself so highlighted in blue are the indices representing the initial segment I represents the left index of the segment and J represents the right when splitting the segment 0 to 3 we find the midpoint by adding indices I and J and dividing the sum by two the midpoint position allows us to compute the new indices for the left and the right segments in the given scenario the midpoint is at index one resulting in the left segment being 0 to 1 and the right segment being 2 to 3. we can reapply the same process to split the left segment again in this case the midpoint is at index 0 and the new Left segment is at 0 and the right segment between one and one both inclusive and similarly for the right segment here the interval 2 to 3 gets broken down into a left segment of two comma two and a right segment of three to three and that's how the splitting process works in a nutshell now let's go back to the pseudocode for a moment now looking at the code again you can see that inside the find maximum element function the first thing we do is check if the list is empty and return null if there are no elements the reason for doing this is that there's no way to divide up an empty array any further so immediately handle this Edge case it also prevents us from having a negative index value on the next line which would cause the recursion to spiral into a stack Overflow error on the next line you can see that we're calling the fine Max function below which is what actually finds the maximum the input to this function takes two indices I and J which represent the segment of the array which we want to find the maximum um four index I is the left endpoint and J is the right endpoint since we want to find the maximum of the whole array we pass an i equals zero as the left most index and J equals the length of the array minus one as the right to most index now let's take a look at what exactly is happening inside the find Max function the first thing we do is check if I is equal to J which means that the size of the segment or interval is a single element since we know that the maximum value for a single element is the element itself we simply return the element at that index and this constitutes our base case next in order to split the segment in half we need to find the middle index position between I and J this allows us to split the current segment into two parts a left segment from I to the midpoint and a right segment from the midpoint to J then on the next line you can see that this is where we do both the segment split and then the combination of sacraments on the Callback the first to find Max function we call it corresponds to the left segment and the second call to the right segment since the indices for the segments is inclusive the left segment ranges I to Mid but to avoid an overlap the right cycle band starts at Mid plus one and ends at J and that's how you use dividing conquer to find the maximum element in a list

all right so we just finished taking a look at how to use Divine conquer to find the maximum element in the list the strategy we looked at repeatedly divided the segments into two parts for this challenge I want you guys to modify the previous code example to return the minimum value in the list while doing a three-way search instead of a two-way search for example in the list here we divide the nine elements into three segments of length three and then we further divide up those segments to three more segments of length one each we can then find the minimum value of the whole list based on the method of splitting the same way we did previously so before you guys go ahead and try and implement this I want to give you all a hint in the two-way split example we split the segment in half based on a single midpoint now we want to split the segment into three parts which means that we will need two midpoints instead of a single midpoint all right I'm going to give you guys a moment to pause the video if you want to give us a try I'm going to reveal a solution in the next slide awesome I hope you guys were able to give that a try and here's one way to implement the three-way split using uh Divine Conker strategy we just talked about so rather than having a single base case I address three different base cases when the size of the interval is three or smaller in these cases simply return the minimum of the existing values this approach simplifies handling the scenarios where the interval consists of precisely three elements or cannot be divided any further if none of these base cases are encountered we know that our interval comprises of four or more elements when the interval is we can split the current interval into three segments since we want three separate segments there has to be two different midpoints by which we can split across these midpoints can be found at the one-third Mark and at the two-thirds mark once we have our midpoints we can then split the current segment into roughly equal thirds and return the minimum value found in the list awesome guys that's all I have for now on Divine conquer in the next video so we'll be taking a look at merge sort and binary search both of which use the divide and conquer Paradigm as a central component to the solution thanks again for watching please like And subscribe and I'll catch you in the next one cheers foreign