We say it's starting with the letter M, we know that the word,

teacher, starts with a T and T is to the right of M in the dictionary.

So then, we go to the right half of the dictionary, where, after M.

We also open it arbitrarily and look at what, the word we saw there.

If we look at that word, might be a letter U, starting with letter U.

Okay, we said we, we, we went too far to the right, because we are now at letter U.

That's after letter T.

Then we go to the left, to the left part there, and look for it, for, for the word.

We keep doing this process until we get to the page that has teacher.

This is not a hypothetical scenario.

This is how you would look up a word in a dictionary.

If you do it really by going from page one to page two,

you are doing a very bad way of looking up words in a dictionary.

Okay?

So, this is how we look up a word in a dictionary.

And the question is, how, how does that change the algorithm for

sorting, for searching, okay?

But notice, there's a very important assumption here,

that the dictionary is already sorted in a lexicographical manner.

This is what allowed me to say when I'm looking for the word teacher,

if I get to a page of starts with, where the word starts with the letter m.

What allowed me to say, I have to go right, is because I

know the dictionary is sorted, and the word teacher is going to be to the right.

Right?

So, the assumption that the dictionary is sorted, is a very

powerful assumption that we can exploit when we are doing the search procedure.

Same thing, if I, you are looking for the Social Security number of an individual in

a list of 300 million Social Security.

And they are sorted, the algorithm should not start from the very first one and

go to the second, and go to the third.

It should go to the middle of that list, and then ask,

is the one I'm looking for before the middle or after the middle?

Because I have an order on these number, I will know whether to go left or right.

If I decide to go right,

I'll go to the middle of that right part and repeat the same process.

So now you can see similar similar in nature to the algorithm to that we

saw in merge sort.

That we are, we want to solve the problem of searching,

I'm doing a divide and conquer.

I'm searching for

the word teacher in dictionary, I'm dividing the dictionary into two halves.

I will look at the words in the half.

They all start with m.

I know that the word teacher is going to be on the right.

So I will now focus on the right half divided into two halves.

Repeating the same process, I will keep dividing until I get to the right page,

and find the word teacher, okay?

So, if I want to do this search on this list, again.

This list I cannot apply this technique I am talking about to.

So I have to assume that I have a sorted list, okay?

So let's look at now, a list that is sorted.

[NOISE] And suppose I am looking for

the key for x equal 50.

Okay?

So I'm looking for x equals 50 in this list that is sorted.

The first thing we do again in divide in conquer is

say I'm not going to look in the entire list, I'm going to divide it in half.

So I'm going to take this list and divide it into two halves.

Now, I have 1, 3, 5, 19 and the second one is going to be 20,

25, 100 and 113, all right?

Now, I know that I'm looking for 50.

I know that for this left half, 19 is the largest.

For the right half, 20 is the smallest.

So, I need to look at 50 and say is it bigger, smaller or

whatever between before these two numbers.

I know that 50 is bigger than 19, right.

50 is bigger than 19, so 50 cannot be here, it has to be in this side.

50 is bigger than 19, therefore it has to be in that side.

I come to this one, and I divide it into two halves, 20, 25, 100, 113.

Unlike merge sort, when I went to this half I am done with this and

I will kill this branch of the tree.

I will never do anything here.

I come to this, to this, now I compare 50.

50 is bigger than 25.

I will say that it cannot be here, it has to be here.

If 50 is here, then I kill this branch, and I come to this one, and

I divide it into 100, and 113.

50 is smaller than this.

There is nothing to the left to return.

I will say, minus 1.

The algorithm got to a list of size 1.

It should have found it there, if anywhere.

It wasn't there, it returns minus 1.

And this algorithm, is known as Binary Search.

Unlike linear search, it's not searching the entire list.

Notice that this algorithm would never check the value on 1, 3, 5.

It looked at 19 and decided to go there.

Once it looked here, it never looked at 20, or 20 for example, and so on.

So binary search is similar to merge sort.

Take the list divide it into a half into two halves, but

unlike merge sort one of the halves it will never touch, right?

In this case, it discarded this.

In this case, it discarded this.

And in this case it discarded this.

And then, it return okay.

So, it divided, conquered and this, there's another thing here also,

there's no merge.

Okay? Once we get here and

we return the value of minus 1.

I don't need to go back up and merge anything.

Okay?

So, these, these are some major differences between binary search and

merge sort.