0:11

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.

Â 3:01

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.

Â 12:34

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.

Â