[MUSIC] So, today I'm going to illustrate the notion of divide and conquer algorithms, and recursive implementation, as a mechanism for reasoning about problems. And I'm going to use the problem, a very common problem, that's used in textbooks, algorithms textbooks, it's called binary search. Or in general the search problems, and the problem is defined as follows. I'm giving a list of numbers. Let's think about it as a list of numbers. And the list is sorted, let's say in ascending order. So I have 5, 7, 9, 15, 27, 35, 100. So I have this list as an input, some, someone gave me this list. And in addition, they're giving me some element k. And that k is, for example, 35. And the question that we want to answer is that, is k in the list L? Okay? So, the first the first approach that one would think about is, okay, I can look at the list, scan the list from left to right, I see okay, 35 is here, so I can say, yes it is there, okay? So I'm going to look at the version the problem where, I will say, yes, or true, the element is in the list, or no, or false. If the element is not in the best. Okay? So the first approach to some problem like this or the native approach, is that just scan the list again. And if I want to write it in, in not real code, but in something, some hybrid between English and real code, which we call pseudocode. And an approach like this. So suppose I have, I have the left starting at position zero, and all the way to position n minus 1. So it has n elements, and [INAUDIBLE] zero to n minus 1. So, one way to, to, to approach this problem, or to solve it, I can say for I equals 0, to n minus 1. If L the ith element, if it is equal to this K that I'm interested in, return true. [SOUND] Else, here, if I, if I have gone through all the elements and haven't found it, I can return false. Okay? So this is an approach actually for solving this problem. It is taking as input this list L, and element K, and it's going to return true if K is found at some index within this list, or it's going to return false, if it's not there. This approach here, because I'm scanning the entire list, this is known as linear, search, okay? Now, you have heard about growth of functions and how, how the running time of algorithms changes as we increase input size. So if I look at the input size here as the size of this list, which is n. And I look at, and I look at, and as it increases from 2, let's say, to 4 to 8 to 16, and so on. You will notice that if I double the size of the list, the running time, roughly, is going to double, right? So, I'm going to be looking at twice the number of elements. If I triple it, it's gon, the running time is going to triple, because I'm going to be looking at three times the number of elements, and so on. Now, this algorithm is fine. Linear running time is good, is fine, no problem with that. But one of the things that this algorithm is discarding, or not taking into consideration, is that I said the list is already sorted, okay, so it is sorted in ascending order. Can we use that fact, to make our algorithm more efficient, okay? And the answer is yes. Think about it for, for a second, just forget about, let's, and think about dictionary. When you are looking for a word in dictionary, the dictionary is sorted, right? I mean, it's sorted alphabetically. Now, when you look up for a, when you look up a word in the dictionary, you don't go from the first page and, the second page and then the third page looking for that. No, we usually open the dictionary to the middle, for example. Roughly the middle. And then we say okay, what is the word that we are looking for? Suppose the word starts with the letter S, and we opened the dictionary and we are at letter M. We know that S comes after M, so we go to the right, of that midpoint. And we repeat this process. Exactly the same idea is going to be applied here. I am looking for this element 35. All right? So, since that list is, is, is sorted, I'll say, I'm not going to scan it linearly, I am going to go to the middle point of this list, which is this point here, okay? So, I'm going to, to go this point, and I'm going to ask, is 35 positioned there, or is the element 35 found at that midpoint of the list? If the, if 35 is there, I am done, I found it already in one operation. I went to that midpoint, and found it there, I am done, I return true. If it's not there, I have one of two choices now. Either 35 or that element I'm looking for, is smaller than the value at the midpoint. Or it is bigger than the value at the midpoint. If it is smaller, so suppose I am looking for element eight, If I'm looking for element eight, of course 15 does not equal eight. Because the list is sorted in ascending order, I know now I need to see if eight is to the left of this number, right, because it's smaller than it, and the list is sorted in ascending order. I am looking for the 35, I go to the midpoint, its not there. I know for sure, that if 35 is in the list, it has to be to the right of this point. If its not to the right, if its in the list and not to the right, then the list is not sorted in ascending order, so that violates my assumption. So, if 35 is to the right, what do I do? Okay, if it's, I want to find if it's to the right of 15. Now, I am going to repeat exactly the same process. I am now going to look at this half of the list. I'm going to go to the midpoint of that half, I am going to check if 35 is there, if it's not there. And smaller than the value, I'm going to go to the left of that midpoint. If it's bigger, I'm going to go to the right of that midpoint. So, since I am doing exactly the same process, and I will repeat it over and over and over, this is exactly where we use recursive implementations. This is a divide and conquer algorithm, because I am dividing the list at every point, I am dividing it into two halves. And then I'm concurring the problem by going either to the left half or to the right half. Whenever I go to the left or to the right, I'm repeating exactly the same process, right? And this is why we use or invoke recursive implementation here. Because I don't have to keep repeating the details of that process. I say, here is a black box that going to, implement some, some some procedure, just keep applying that black box to the left or to the right, depending on answering that simple question, which is is the element smaller than the one, the midpoint, or greater than the element at the midpoint? So, how would I write that algorithm? Again if I want to, if I want to illustrate 35 completely with this, I say okay, here's the midpoint, 35 is not here, it is bigger than 15, so I look at this. So now, I repeat the process on this. What is the midpoint of that? It has three elements, this is the midpoint now. Right? When I go here, I say if 35 equal to this, I found it, I return true, and I'm done, right? So, you keep doing this process. This is a procedure, or this is a description of the algorithm for linear search. How would I do a binary search, how would, how would I implement this? Again, using this, the, this kind of, of coding style, I will define the, the function binary search. [SOUND] That's going to take as input this this, this list or array that's sorted in ascending order, L. It's going to take, in addition, two indices here, and I'm going to call them L and R for left and right, which are giving me the boundaries, so when I call the function in the beginning, they are going to be 0 and n minus 1, if the list has n element. And I have that element K that I'm looking for, okay? Again, this is the list that I'm trying to see if the element is in. This is the element I'm trying to find if it's there. L and R and the left and right boundaries. So when we start with this list. [SOUND] So if I copy this 5, 7, 9, 15, 27, 35, 100. So L, to begin with, L equal 0, and R equals 6, okay? So, L equals 0 and, and, and R equals 6. I'm going to be looking for that, and when I call the function in the beginning, I will be doing binary search [SOUND] on this L, from position 0 to position 6 of that element 35. This is how I'm going to call this, okay? So what are the details of this function? As a sanity check in the beginning, L is the left and R is the right, I want L to be at most equal R, right? So I cannot, I'm not going to accept that L is greater than R. So, as a sanity check first, if we say if L is greater than R. If you pass this, return false. [SOUND] Okay? The element is not there. If it's not this, which means everything is fine. I passed the left and right boundaries legitimate values. Now I need to find the midpoint there, so I will call that M or mid, let's say, and mid I'm going to set it to, I can use left arrow, also in this notation to set a value or to assign a value to this variable mid. I'm going to say it's L plus R divided by 2, okay? Now, just a small detail here, what if again, L is 0 and R is, is 6, so 0 plus 6 is 6, divided by 6 is 3. What if it was 0 and 7? 0 plus 7 is 7, divided by 2 is 3.5. But 3.5 is not the index in the array, so what do I do about that? Here you have to make a decision. You either round it down to 3, or you round it up to 4. Okay, and you have to be consistent about that. So here I'm going to use this notation. Which we call the floor, which will rounded it down. So if this L plus R is 7, 7 divided by 2 is 3.5, the floor of that is 3. Okay, so this value of mid is going to be 3. Then once we have, I found this mid point, I ask a simple question, is K equal to the value at the midpoint? [SOUND] Is it equal to that? If that, if that's the case, we have none. I return true. If it's not, again, now I need to see is, is the element smaller than the value at the midpoint or bigger? If, the element is smaller than the midpoint. Then, I have to repeat exactly the same process, which is binary search, on the left half. So if this is the midpoint, I need now to repeat it on this, but what are the boundaries of this? L doesn't change. We still have L here. And this is mid minus 1. Right? So now I have to repeat binary search. [SOUND] On the same list, but now I take the boundaries to be a L and mid, minus 1, and I'm still looking for the same value. Else, if K is greater than the midpoi, the value at the midpoint, then else, I can do binary search [SOUND] L, but now I need to do it on this part here. So it's from mid plus 1, right? 2R, so I need to do it, so them the, the left boundary is the entry next to the midpoint, which is mid, at mid plus 1, all the way to R. And I'm looking for K, okay? So this is, this is the algorithm that will do this binary search on this list. Notice that I am calling the same function. Okay? Which is a recursive call. The only thing that changes is what are the boundaries, while I am looking at that element, right? So, am I looking at the left half or the right half? And when I repeat the process, when I go to the left half, I go either to the left of that left have or the right of the, that ri left half. But I repeat the same process over and over, and this is an example of binary search, and this is how we would write it recursively, okay? I am not going to go through mathematical details here. But, as an exercise, it's a bit of challenging exercise based on the materials we have covered so far, you can see that the running time, whereas this is linear, if you double the the running ti, if you double the size of the input, you double the running time, here you will see that if you take n, for example, and you go from n equal 8, to n equals 16, in terms of the input. So if you start with a list that has eight elements, verses a list of 16 elements, you will find that here, you will be doing roughly about three operations, if you do this, you are going to go to four operations, if you go to 32, so I am doubling, I'm going to go to five. So I'm doubling the input, but whenever, the input size, whenever I double the input size, the running time is increasing only by one operation, oaky? And this growth is actually log of n, where when, when n is the size of the list. So, this algorithm, this binary search, is much better than linear search, in terms of running time. Instead of doing linear time, we are doing it logarithmic time, which grows much slower than linear time. But, I want to remind you once again, that whereas linear search works on any list, for finding an element, binary search, a very important precondition for this to work, is that the list has to be sorted.
