0:00

So, now we have talked about the sorting problem.

Â We tried the naive approach that took o of n squared.

Â Then we looked at merge sort, which takes o of n log n.

Â This algorithm illustrated very nice techniques in algorithms and math.

Â First, we saw divide and conquer.

Â How to take a problem and divide it into, to sub problems and, and

Â continue to solve these sub problems.

Â The second thing we saw, is that in a mathematical tool of

Â how we analyze these kind of algorithms that are implemented recursively.

Â Remember that, or notice that, you know, divide and

Â conquer algorithms do not have to be implemented recursively.

Â You can still implement it in,

Â in a non-recursive manner, but recursion, I would, I would say that,

Â is the natural way to implement a divide and conquer algorithm.

Â And it is usually much more elegant and much nicer to implement a divide and

Â conquer algorithm in a recursive manner.

Â So then we saw that for a recursive implementation,

Â when we analyze the running time, it gives rise to these nice recurrences and

Â then we can use a tool like the master theorem to get o of n log n.

Â 1:03

Continuing with this theme, but

Â focusing on a different problem that we had talked about, which is searching.

Â Now, search is a very important problem.

Â We always do search.

Â You always do a Google search, you always, the, the administrators at

Â the university are always doing search queries for records of a student.

Â You go to the store and you are, you ask a person in the store if they have,

Â if they carry a certain item, they have to search their inventory.

Â Their search is going to be basically searching an, an,

Â a key, which you told them.

Â You know, I'm searching for

Â item x, they have to search it against the, the entire inventory that they have.

Â So the question is, algorithmically, how do we do the search?

Â I would say by probably this is an even easier problem than sorting.

Â It is such a fundamental problem in so many applications.

Â Again, it's not of, the, the most famous application because it's

Â not doing really what we are seeing in, in the powerful applications.

Â But under, under the hood, it is one of the,

Â the important engines that, that that powers so many applications.

Â So now when we talk about the searching problem, what is the input?

Â In the case of sorting, the input was a list, and

Â the output was, I want it to be sorted.

Â Here in the case of, of searching, what is the input to the problem?

Â Usually it is a list of items, and have an ender key.

Â An additional key, or an additional item.

Â I want to search for that item to see if it is in the list.

Â If it is in the list, I want to return the index or

Â the place of that item in the list.

Â If it's not, for example, convention is to return say it is minus one.

Â That it is not found there, it is in position minus one, which does not exist.

Â So for a searching problem, again, I'm given a list of 1,

Â 7, 5, 3, 19, 100, and 17.

Â So I have, and 25, I have this list, L.

Â 2:59

And in addition, I have an element x here that can be for example 19.

Â And I'm say, saying search for x on this list and tell me the location of it.

Â If it's found, if it's not found, tell me that it is minus 1.

Â So, how do we solve this?

Â If I, if someone come up to you and say, give me an algorithm implemented in

Â whatever programming language, that will solve this problem.

Â Right?

Â I am sure you're going to be able to solve it.

Â And I'm sure you're going to give the algorithm that every textbook has,

Â by basically looking at item x.

Â Going through this list one item at a time, saying, is 19 equal to 1?

Â No.

Â Is 19 equal to 7?

Â No, is 19 equal to 5?

Â No.

Â To 3?

Â No.

Â To 19?

Â Yes.

Â 19 is at position four.

Â If I am indexing things from 0, 1, 2, 3, 4,

Â you're going to say it is in position four, you're going to return four.

Â So this will be your algorithm.

Â If I am searching for item Y let's say it is ten.

Â I'm going to go say is it 10 equal to 1?

Â No.

Â To seven?

Â No.

Â Five? No.

Â Three? No.

Â I will go and continue here.

Â It's not there.

Â I will return minus 1.

Â Okay?

Â This algorithm is a very common algorithm and it is called Linear Search.

Â Okay?

Â So this algorithm is called Linear Search.

Â And if you think about it for, for five seconds, you will, you can be,

Â you can, you, you'll be able to tell why it is called Linear Search.

Â Because actually the running time of this algorithm is going to be linear in

Â the list size, right?

Â In the worst case, the item you are looking for is not here.

Â You will have to be looking across all of them.

Â What is the algorithm doing?

Â It's just looping through the list, and ev, for every item, at the i,

Â that index, it's comparing it to the key we are searching for.

Â So this linear search takes o of n amount of time, okay?

Â 6:21

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.

Â