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.