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. 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. 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? So are we done? Is this all we wanted to say about searching? If you think about it, no, because if this was all we wanted to say about searching, we wouldn't have covered it, okay? It is very often the case that when you are doing searching, in practice in against a database or against a list or in an Excel sheet. That the sheet or the database or the list of items is already sorted. It is already sorted. Again, when I'm looking up a word in the dictionary, just think about that case and think about the real dictionary, okay. Because when you, if you have an online dictionary and you type a word, you are not seeing anything about how the algorithm does the searching. But if you really look up a word in a dictionary, suppose I say look up the word teacher in a dictionary. I am, I'm sure you aren't going to go to that dictionary and start with page one, and say, okay, is teacher here, and then go to page two, then page three. Keep going until you get to the page that has the word teacher. You are not going to do this. The way we look up a word in a dictionary, we randomly open the dictionary at some point, right? I mean we open the dictionary, for example, to page 200, right? Then we look at that page and we say okay, what words are on that page? We say, okay, at that page, we, when we opened the page, it is actually at the words that start with letter M. 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.
