CS50x 2026 - Lecture 3 - Algorithms

Key Takeaways

Heat. [music] Heat. [music] >> [music] [music] >> Damn. by black. Black [music] Why? Why? Why? Why? Why? Why? Why? Heat. Heat. [music] [music] All right, this is CS50. This is week three. And this was an artist rendition of what various sorting algorithms look and sound like. Recall from week zero that an algorithm is just step-by-step instructions for solving some problem to sort information as in the real world just means to order it from like smallest to largest or alphabetically or some other heruristic. And it's among the algorithms that we're going to focus on today in addition to searching which of course is looking for information as we did in week zero too. Among the goals for today are to give you a sense of certain computer science building blocks. Like there's a lot of canonical algorithms out there that most anyone uh who studied computer science would know, who anyone who leads a tech interview would ask. But more importantly, the goal is to give you different mental models for and methodologies for actually solving problems by giving you a sense of how these uh real world algorithms can be translated to actual computers that you and I can control. We thought we'd begin today uh with an actual algorithm for sort of taking attendance. We of course do this with scanners outside, but we can do it old school whereby I just use my hand or my mind and start doing 1 2 3 4 5 6 7 8 9 10 11 12 and so forth. That's going to take quite a few steps cuz I've got to point at and recite a number for everyone in the room. So I could kind of do what my like grade school teachers taught me, which is count by twos, which would seem to be faster. So like 2 4 6 8 10 12 14 16 18 20. And clearly that sounds and is actually faster. But I think with a little more intuition and a little more thought back to week zero, I dare say we could actually do much better than that. So if you won't mind, I'd like you to humor us by all standing up in place and think of the number one if you could and join us in this here algorithm. So stand up in place and think of the number one. So at this point in the story, everyone should be thinking of the number one. Step two of this algorithm for you is going to be this. Pair off with someone standing. Add their number to yours and remember the sum. Go. Okay. At this point in the story, everyone except maybe one lone person if we've got an odd number of people in the room is thinking of what number? >> Two. Okay. So next step, one of you in each pair should sit down. Okay, good. Never seen some people sit down so fast. So those of you who are still standing, the algorithm still going. So the next step for those of you still standing is this. If still standing, go back to step two. Airgo repeat or loop if you could. And notice if you've gone back to step two, that leads you to step three. That leads some of you to step four, which leads you back to step two. So this is a loop. Keep going. If still standing, pair off with someone else still standing. Add together and then one of you sit down. So with each passing second, more and more people should be sitting down and fewer and fewer standing. Okay, almost everyone is sitting down. You're getting farther and farther away from each other. That's okay. I can help with some of the math at the end here. All right, I see a few of you still standing, so I'll help out and I'll I'll join you together. So, I see you in the middle here. What's your number? >> 32. >> 32. Okay, go ahead and sit down and I'll pair you off with What's your number? >> 20. Okay, you can go ahead and sit down. Uh, who's still? You're still standing. >> 27. >> 27. Okay, you can sit down. >> You guys are still adding together. Who's going to stay standing? Okay, what's your number? >> The worst part is doing like arithmetic across a crowded room, but >> 27. >> 27 also. >> 47. >> 47. Okay, you can sit down. Is anyone still standing? Yeah, >> 15. >> Nice. 15. Okay, you can sit down. Anyone still standing? Okay, so all I've done is sort of automate the process of pairing people up at the end here. When I hit enter, we should hopefully see Oh, the numbers are a little What's going on there? There we go. When I hit enter, we'll add together all of the numbers that were left. And if you think about the algorithm that we just executed, each of you started with the number one, and then half of you handed off your number. Then half of you handed off your number. Then half of you handed off your number. So theoretically all of these ones with which we started should be aggregated into the final count which if this room weren't so big would just be in one person's mind and they would have declared what the total number of people in the room is. I'm going to speed that up by hitting enter on the keyboard. And if your execution of this algorithm is correct, there should be 141 people in the room. According to our old school human though, Kelly, who did this manually, one at a time, the total number of people in the room, according to Kelly, if you want to come on up and shout it into the microphone, is of course going to be >> I don't know, something around 160, I think. >> 160. So, not quite the same. Okay, but that's pretty good. Okay, round of applause for your your accuracy. [applause] Okay, so ideally counting one at a time would have been perfectly correct. So, we're only off by a little bit now. Presumably, that's just because of some bugs in execution of the algorithm. Maybe some mental math didn't quite go according to plan. But theoretically, your third and final algorithm wherein you all participated should have been much faster than my algorithm or Kelly's algorithm, whether or not we were counting one at a time or two at a time. Why? Well, think back to week zero when we did the whole phone book example, which was especially fast in its final form because we were dividing and conquering, tearing half of the problem away, half of the problem away. And even though it's hard to see in a room like this, it stands to reason that when all of you were standing up, we took a big bite out of the first problem and half of you sat down, half of you sat down, half of you sat down, and theoretically there would have been, if you were closer in in uh space, one single person with the final count. So let's see if we can't analyze this just a little bit by considering what we did. So here's that same algorithm here, recall is how we motivated week zero's demonstration of the phone book in either digital form as you might see in an iPhone or Android device looking for someone for instance like John Harvard who might be at the beginning, middle or end of said phone book, but we analyze that algorithm just as we can now this one. So in my very first verbalized algorithm 1 2 3 4, you could draw that as a straight line because the relationship between the number of people in the room and the amount of time it takes is linear. It's a straight line with each additional person in the room. It takes me one more step. So if you think to sort of high school math, there's sort of a slope of one there. And so this n number denoting number of people in the room is indeed a straight line. And on the x-axis as in week zero, we have the size of the problem in people and the time to solve in steps or seconds or whatever your unit of measure is. If and when I started counting two at a time, 2 4 6 8 10 and so forth, that still is a straight line because I'm taking two bytes consistently out of the problem until maybe the very end where there's just one person left, but it's still a straight line, but it's strictly faster. No matter the size of the problem, if you sort of draw a line vertically, you'll see that you hit the yellow line well before you hit the red line because it's moving essentially twice as fast. But that third and final algorithm, even though in reality it felt like it took a while and I had to kind of bring us to the exciting conclusion by doing some of the math, that looked much more like our third and final phone book example because if you think about it from an opposite perspective, suppose there were twice as many people in the room. Well, it would have taken you all theoretically just one more step. You know, granted, one more loop and there might be some substeps in there, if you will, but it's really just fundamentally one more step. If the number of people in the room quadrupled, four times as many people, well, that's two more steps. Equivalently, the amount of time it takes to solve the attendance problem using that third info algorithm grows very slowly because it takes a huge number of more people in the room before you even begin to feel the impacts of that uh growth. And so today indeed, as we talk about not only the correctness of algorithms, we're going to talk about the design of algorithms as well. Just as we have code, because the smarter you are with your design, the more efficient your algorithms ultimately are going to be and the slower their cost is going to grow. And by cost, I mean time like here, maybe it's money, maybe it's the amount of storage space that you need, any limited resources, something that we can ultimately measure. And we're not going to do it very precisely. Indeed, we're going to use some broad strokes and some standard mechanisms for describing ultimately the running time, the amount of time it takes for an algorithm or in turn code to actually run. So, how can we do this? Well, last week recall we set the stage uh for talking about something called arrays, which were the simplest of data structures inside of a computer where you just take the memory in your computer and you break it up into chunks and you can store a bunch of integers, a bunch of strings, whatever, back to back to back to back. And that's the key characteristic for an array. It is a chunk of memory wherein all of the values therein are back to back to back. So right next to each other in memory. So we drew this fairly abstractly by drawing a grid like this. And I said, well maybe this is by zero and this is by 1 billion. Whatever the total number amount of memory is that you have. We zoomed in and looked at a little something like this, a canvas of memory. We talked about what and where you can put things. But today, let's just assume that we want 1 2 3 4 5 6 seven chunks of memory for the moment. And inside of them, we might put something like these numbers here. Well, the interesting thing about computers is that even though if I were to ask you all, find the number 50 in this array. I mean, our eyes quickly see where it is because we sort of have this bird's eye view of the whole screen and it's obvious where 50 is. But the catch with computers and with code that we write is that really these arrays, these chunks of memory are equivalent to a whole bunch of closed doors. And the computer can't just have this bird's eye view of everything. If the computer wants to see what value is at a certain location, it has to do the metaphorical equivalent of going to that location, opening the door, and looking, then closing it, and moving on to the next. That is to say, a computer can only look at or access one value at a time. Now that's in the simplest form. You can build fancier computers that theoretically can do more than that. But all the code we write generally is going to assume that model. You can't just see everything at once. You have to go to each location in these here lockers, if you will. Starting today too when we talk about the locations in memory. We're going to use our old uh zero indexing uh vernacular. That is to say, we start counting from zero instead of one. So this will be locker zero, locker one, locker two, dot dot dot all the way up to locker six. So just ingrain in your mind that if you hear something like location six, that's actually implying that there's at least seven total locations because we started counting at zero. So that's intentional. Um we don't have in the real world yellow lockers. So we're going to make this metaphor red instead. We do have these lockers here. And suppose that within these seven lockers physically on stage, we've put a whole bunch of money, uh monopoly money, if you will. But the goal initially here is going to be to search for some specific denomination of interest and use these physical lockers as a metaphor for what your computer's going to do and what your code ultimately is going to do. If we're searching for the solution to a problem like this, the input to the problem at hand is seven lockers, all of whose doors are metaphorically closed. The output of which we want to be a bull, true or false answer, yes or no, that number is there or no, it is not. So, inside of this black box today is going to be the first of our algorithm, step-by-step instructions for solving some problem where the problem here is to find among all of these dollar bills, specifically the $50 bill. If we could get two volunteers to come on up, who are ideally really good at Monopoly? Okay, how about over here in front? And uh how about let me look a little farther in back. Okay, over here there and back. Come on down. All right. As these uh volunteers kindly come down to the stage, we're going to ask them in turn to search for specifically the $50 bill that we've hidden in advance. And if uh my colleague Kelly could come on up too because we're going to do this twice. Once searching uh in one with one algorithm and a second time with another. Uh let me go ahead and say hello if you'd like to introduce yourselves to the group. >> Hey, I'm Jose Garcia. >> Hi, I'm Caitlyn Cow. >> All right, Jose and Caitlyn. Nice to meet you both. come on over and let me go ahead and propose that Jose um the first algorithm that I'd like you to do is to find the number 50 and let's keep it simple. Just start from the left and work your way to the right. And with each time you open the door, stand over to the side so people can see what's inside and just hold the dollar amount up for the world to see. All right, the floor is yours. Find us the $50 bill. 20. >> Shut it. >> No, that's good. That's good acting, too. Thank you. No, you can shut it just like the computer. All right. No. Very clear. Thank you. Still no. $10 bill. Next locker. $5 bill. Not going well. Uh $100 bill, but not the one we want. This one. Ah, $1 bill. Still no 50. Of course, you've been sort of set up to fail, but here, amazing. A round of applause. Jose found the $50 bill. [applause] All right. So, let me ask you, Jose, you found the $50 bill. Um, it clearly took you a long time. Just describe in your own words, what was your algorithm, even though I nudged you along? >> Yeah. So, my algorithm was basically walk up to the first door available, open it, check if the dollar bill was the dollar bill that I was looking for, and then put it back, and then go to the next one. >> Okay. So, it's very reasonable because if the $50 bill were there, Jose was absolutely going to find it eventually, if slowly. In the meantime, Kelly's going to kindly reshuffle the numbers behind these doors here. And even though Jose took a long time here, I mean, what if Jose like wouldn't have been smart to start from the other end instead, do you think? >> Um, not necessarily because we don't know if the 50 is going to be at that end. >> Exactly. So, he could have gotten lucky if he sort of flaunted my advice and didn't start on the left, but instead started on the right. Boom. he would have solved this in one step. But in general, that's not really going to work out. Maybe half the time it will. You'll get lucky, half the time it won't. But that's not really a fundamental change in the algorithm whether you go left to right, right to left. To Jose's point, if you don't know anything priori about the numbers, the best you can probably do is just go through linearly left to right, or right to left, so long as you're consistent. Now, could you have jumped around randomly? >> Uh, I guess I could have, but if again, if they weren't in any like specified order, I don't think it would have helped either. Yeah. So, and additionally, if he just jumped around to random order, they might get lucky and it might be in the very first one. Might have taken fewer steps ultimately, but presumably you're going to have to then keep track of like which locker doors have you opened. So, that's going to take some memory or space. Not a big deal with seven lockers, but if it's 70 lockers, 700 lockers, even random probably isn't going to be the best job. So, let me go ahead and take the mic away and hand it over to Caitlyn. You can stay on the stage with us. Caitlyn, what I'd like you to do is approach this a little more intelligently by dividing and conquering the problem, but we're going to give you an advantage over Jose. Kelly has kindly sorted the numbers from smallest to largest from left to right. >> So, accordingly, what's your strategy going to be? >> Start in the middle. >> Okay, please. And go ahead as before and reveal to the audience what you found. Not the 50, the 20. But what do you know, Caitlyn, at this point? >> It'll be in on the left. Left. Correct. So the 20 is going to be to the left. So where might you go next with this three locker problem? Let me propose that you maybe go to the middle of the three. >> There we go. The middle of the middle. Like that would have been good. But let's >> Oh no. >> Oh no. It's a 100 instead. You failed. But what do you now know? >> It's in the middle. >> That I should have just let you. But now we have a big round of applause for Kaylin for having found the 50 as well. [applause] Okay. So, the one catch with this particular demo is that because they know presumably what monopoly money denominations are because we just did this exercise and we had the whole cheat sheet on the board, you probably had some intuition as to like where the 50 was going to be, even though I was trying to get you to play along. But in the general case, if you don't know what the numbers are and that they're the specific denominations, but you do know that they're going from smallest to largest, going to the middle, then the middle of the middle, then the middle of the middle again and again would have the effect of starting with a big problem and having it, having it, having it, just like the phone book as well. So, thanks to you both. We have these wonderful parting gifts that we found in Harvard Square. Uh, if you like Monopoly, you'll love the Cambridge edition filled with Harvard Square name spots. So, thank you to you both. And a round of applause for our volunteers here. [applause] All right, so let's see if we can't formalize a little bit these two algorithms known as linear search in so far as Jose was searching essentially along a line left to right and binary search by implying two because we were having that problem in two again and again and again. So for instance with linear search from left to right or equivalently right to left we could document our pseudo code as follows. For each door from left to right if the 50 is behind the door well then we're done. Just return true. That's the boolean value which was the goal of this exercise to say yes here is the 50. Otherwise at the very bottom of this pseudo code we could just say return false. Because if you get all the way through the lockers and you have never once declared true by finding the 50, you might as well default at the very end to saying false. I did not find it. But notice here, just like in week zero when we talked about pseudo code for searching the phone book, my indentation of all things is actually very intentional. This version of this code would be wrong if I instead used our old friend if else and made this conditional decision. Why is this code now in red wrong in terms of correctness? Yeah, if it's not behind the first door, it will return false. >> Exactly. Because if the number 50 is not behind the first door, the else is telling you right then and there, return false. But as we've seen in CC code, whenever you return a value, like that's it for the function. It is done doing its work. And so if you return false right away, not having looked at the other six lockers, you may very well get the answer wrong. So the first version of the code where there wasn't an else but rather this implicit line of code at the very or this explicit line of code at the very end that just says if you reach this line of code return false that addresses that problem and to be clear even though it's right after an indented return true when you return a value as in C that's it like execution stops at that point at least for the function or in this case the pseudo code in question. All right, so here's a more computer sciency way of describing the same algorithm. And even though it starts to look a little more arcane, the reality is when you start using variables and sort of standard notation, you can actually express yourself much more clearly and precisely even though it might take a little bit of practice to get used to. Here is how a computer scientist would express that exact same idea. Instead of saying for each door from left to right, we might throw some numbers on the table. So for i a variable apparently from the value zero on up through the value n minus one is what this shorthand notation means if 50 is behind doors bracket i so to speak. So now I'm sort of treating the notion of doors as an array using our notation from last week. If 50 is behind doors bracket I return true. Otherwise if you get through the entirety of that array of doors you can still return false. Now notice here n minus one seems a little weird because aren't there n doors? Why do I want to go from 0 to n minus one instead of 0 to n? Yeah, >> because zero is the first locker. >> Exactly. If you start counting at zero and you have n elements, the last one is going to be addressed as n minus one, not n because if it were n, then you actually have n + one elements, which is not what we're talking about. So again, just a standard notation and it's a little turser this way. It's a little more succinct and frankly it's a little more adaptable to code. And so what you're going to find is that as our problem sets and programming challenges that we assign sort of get a little more involved, it's often helpful to write out pseudo code like this using an amalgam of English and C and eventually Python code because then it's way easier after to just translate your pseudo code into actual code if you're operating at this level of detail. All right. So, in the second algorithm, where Caitlyn kindly searched for 50 again, but Kelly gave her the advantage of sorting the numbers in advance. Now, she doesn't have to just resort to brute force, so to speak, trying all possible doors from left to right. She can be a little more intelligent about it and pick and choose the locker she opens. And so, with binary search, as we call that, we could implement the same pseudo code. We could implement pseudo code for it as follows. We might say if 50 is behind the middle door, then go ahead and return true. Else if it's not behind the middle door, but 50 is less than that number behind the middle door, we want to go and search the left half. So that didn't happen in Caitlyn's sense because we ended up going right. So that's just another branch here. Else 50 is greater than what was at the middle door. We want to search the right half. But there's going to be one other condition here that we should probably consider, which is what is it here? Is it to the left? Or is it to the right? But there's another a corner case that we'd better keep track of. What else could happen? >> If it's not in the array or really like we're out of doors, so we can implement this in a different way. I left myself some space at the top because I shouldn't do any of this if there are no doors to search for. So, I should have this sort of sanity check whereby if there's no doors left or no doors to begin with, let's just immediately return false. And why is that? Well, notice that when I say search left half and search right half, this is implicitly telling me just do this again. Just do this again, but with fewer and fewer doors. And this is a technique for solving problems and implementing algorithms that we're going to end today's discussion on. Because what seems very colloquial and very straightforward, okay, search the left half, search the right half, is actually a very powerful programming technique that's going to enable us to write more elegant code, sometimes less code to solve problems such as this. And more on that in just a little bit. But how can we now formalize this using some of our array notation? Well, it looks a little more complicated, but it isn't really. Instead of asking questions in English alone, I might say if 50 is behind doors bracket middle, this pseudo code presupposes that I did some math and figured out what the numeric address, the numeric index is of the middle element. And how can I do that? Well, if I've got seven doors and I divide by two, what's that? 7ide by two, three and a half. Three and a half makes no sense if I'm using integers to address this. So maybe we just round down. So three. So that would be locker number 01 2 3 which indeed if you look at the seven lockers is in fact the middle. So this is to say using some relatively simple arithmetic I can figure out what the address is the index is of the middle door if I know how many there are and I divide by two and round down. Meanwhile, if I don't find 50 behind the middle door, let's ask the question. If 50 is less than the value at the middle door, then let's search not the left half per se in the general sense. More specifically, search doors bracket zero through doors bracket middle minus one. Otherwise, if 50 is greater than the value at the middle door, go ahead and search doors bracket middle + one through doors bracket n minus one. Now let's consider these in turn. So searching the left half as we described this earlier seems to line up with this idea like s start searching from doors bracket zero the very first one. But why are we searching doors bracket middle minus one instead of doors bracket middle. Yeah. >> Yeah. Exactly. We already checked the middle door by asking this previous question. And so you're just wasting everyone's time if you divide the half and still consider that door as checkable again. And same thing here. We check middle plus one through the end of the lockers array because we already checked the middle one. So same reason even though it just kind of complicates the look of the math, but it's really just using variables and arithmetic to describe the locations of these same lockers. But let's consider now what we mean by running time. The amount of time it takes for an algorithm to run. and consider which and why one of these algorithms is better than the other. So in general when talking about running time we can actually use pictures like this. This is not going to be some like very low-level mathematical analysis where we count up lots of values. It's going to be broad strokes so that we can communicate to colleagues uh to other humans generally whether an algorithm is better than another and how you might compare the two. So here for instance is a pictorial analysis of two different algorithms. the phone book from week zero and then the attendance taking from today itself. And let's generally, as we've done before, sort of label these things. So the very first algorithm took n steps in the very worst case if I had to search the whole phone book or if I had to count everyone in the room. So the first algorithm took indeed n steps. The second algorithm took half as many plus one maybe, but we'll keep it simple. So we'll call that n /2. And the third and final algorithm both in week zero with the phone book and today with attendance is technically log base 2 of n. And if you're a little rusty in your logarithms, that's fine. Just take on faith that log base 2 alludes to taking a problem of size n and dividing it in half and half and half as many times as you can until you're left with one person standing or one page in the phone book. That's how many times you can divide in half a problem of size n. Well, it turns out that we're getting a little more detailed than most computer scientists t care to get uh when describing the efficiency of algorithms. So in fact we're going to start to use some note comment notation instead of worrying precisely mathematically about how many steps today's and the futures algorithms take we're going to talk in broader strokes about how many steps they are on the order of and we're going to use what's called big O notation which literally is like a big O and then some parenthesis and you pronounce it big O of such and such. So the first algorithm seems to be in big O of N which means uh it's on the order of N steps give or take some. this algorithm here, you might be inclined to do something similar. Ah, it's on the order of n / two steps and ah, this one's on the order of log base 2 of n steps. But it turns out what we really care about with algorithms is how the time grows as the problem itself grows in size. So the bigger n gets, the more concerned we are over how efficient our algorithm is. if only because today's computers are so darn fast. Whether you're crunching a thousand numbers or 2,000 numbers, like it's going to take like a split second no matter what. But if you're crunching a thousand numbers versus a million numbers versus a billion numbers, like that's where things start to actually be noticeable by us humans and we really start to care about these values. So in general, when using big O notation like this, you ignore lower order terms or equivalently, you only worry about the dominant term in whatever mathematical expression is in question. So big O of N remains big O of N. Big O of N over two. Eh, it's the same thing really as like big O over N. Like it's not really, but they're both linear in nature. One grows at this rate. One grows at this rate instead, but it's for all intents and purposes the same. They're both growing at a constant rate. This one too, ah, it's on the order of log of n where the base is who cares. In short, what does this really mean? And well, imagine in your mind's eye that we were about to zoom out on this graph such that instead of going from zero to like a million, maybe now the x-axis is 0 to a billion. And same thing for the y-axis, 0 to a million. Let's zoom out. So you're seeing zero to a billion. Well, in your mind's eye, you might imagine that as you zoom out, essentially things just get more and more compressed visually because you're zooming out and out and out, but these things still look like straight lines. This thing still looks like curved lines, which is to say as n gets large, clearly this green algorithm, whatever it is, is more appealing, it would seem, than either of these two algorithms. And if we keep zooming out, like at some point, the ink is going to be so close together that they all for are for all intents and purposes pretty much the same algorithm. So this is to say computer scientists don't care about lower order terms like divide by two or base 2 or anything like that. We look at the most dominant term that really matters as n gets bigger and bigger. So that then is bigo notation and it's something we'll start to use pretty much recurringly anytime we analyze or speak to how good or how bad some algorithm is. So here's a little cheat sheet of common running times. So for instance here's our friend big O of N which means uh the algorithm takes on the order of n steps. Uh here is one that takes on the order of log n steps. Here are some others we haven't seen yet. Some algorithms take n times log n steps. Some algorithms take n squared steps. And some algorithms just take one step maybe or maybe two steps or four steps or 10 but a constant number of steps. So let me ask of the algorithms we've looked at thus far for instance linear search being the very first today what is the running time of linear search in big O notation that is to say if there's n people if there's n lockers on the stage how many steps might it take us to find a number among those n lockers big O of yeah big O of N in fact is exactly where I would put linear your search. Why? Well, if you're using linear search in the very worst case, for instance, the number you're looking for, as with Jose, might be all the way at the end. So, you might get lucky. It might not be at the very end, but generally, it's useful to use this big O notation in the context of worst case scenarios because that really gives you a sense of how badly this algorithm could perform if you just get really unlucky with your data set. So e even though big O really just refers to an upper bound like how many steps might it take it's generally useful to think about it in the context of like the worst case scenario like ah the number I care about is actually way over here but what about binary search even in the worst case so long as the data is sorted how many steps might binary search take by contrast >> big O of login so binary search we're going to put here which is to say that in general and especially as n gets large binary search is much faster it takes much less time. Why? Because assuming the numbers are sorted, you will be dividing in half and half and half just like with the phone book in week zero that problem and you will get to your solution much faster. Why should you not use binary search though on an unsorted array of lockers like a random set of numbers? Yeah, >> you can just get rid of the value because you don't know like what the inequality is going to be. >> Exactly. You're making these decisions based on inequalities, less than or greater than, but based on like no rhyme or reason. You're going left, going right, but there's no reason to believe that smaller numbers are this way and bigger numbers are that way. So, you're just making incorrect decision after incorrect decision. So, you're probably going to miss the number altogether. So, binary search on an unsorted array is just incorrect. Incorrect usage of the algorithm. But like Kelly did, if you sort the data in advance or you're handed sorted data, well, then you can in fact apply binary search perfectly and much more efficiently. >> I have a question. Is there ever a case where linear search is more efficient just because the process of sorting the data yourself? >> Absolutely. Is linear search sometimes more efficient if it's going to take you more time to sort the data and then use binary search? Absolutely. And that's going to be one of the design decisions that underlies any implementation of an algorithm because if it's going to take you some crazy long time not to sort like seven numbers but 70 700 7,000 7 million but you only need to search the data once then what the heck are you doing? Like why are you wasting time sorting the data if you only care about getting an answer once? You might as well just use linear search or heck do it even randomly and hope you get lucky if you don't care about reproducing the same result. Now in general that's not how much of the world works. For instance, Google's working really hard to make faster and faster algorithms because we are not searching Google once and then never again doing it. we're doing it again and again and again. So they can amvertise, so to speak, the cost of sorting data over lots and lots of searches, but sometimes it's going to be the opposite. And I think back to graduate school where I was often writing code to analyze large sets of data. And I could have done it the right way, sort of the CS50 way by fine-tuning my algorithm and thinking really hard about my code. But honestly, sometimes it was easier to just write really bad but correct code, go to sleep for 7 hours, and then my computer would have the answer by morning. The downside, as admittedly happened more than once, is if you have a bug in your code and you go to sleep and then seven hours later you find out that there was a bug, you've just wasted the entire evening. So there too, a trade-off sometimes when making those resource decisions. But that's entirely what today is about making informed decisions and sometimes maybe it's smarter and wiser to make the more expensive decision, but not unknowingly, at least knowingly. All right, so there might we have our first two algorithms, but let's consider another way of describing the efficiency of an algorithm. Big O is an upper bound. Sort of how bad can it get in these uh cases where maybe the data is really uh not working to our advantage. Omega, a capital omega symbol here is used for lower bounds. So maybe how lucky might we get in the best case, if you will. How few steps might an algorithm take? Well, in this case here, here's just a cheat sheet of common runtimes, even though there's an infinite number of others, but we'll generally focus on uh um u functions like these. Let's consider those same algorithms. So with linear search from left to right, how few steps might that algorithm take? For instance, in like the best case scenario. Yeah. Is this hand about to go up? >> Yeah. So one step. Why? Because maybe Jose could have gotten lucky and opened this door and voila, that was the 50. It didn't play out that way, but it could have. In the general case, the number you're looking for could very well be at the beginning. So we're going to put linear search at omega of one. So one step and maybe it's technically a few more than that, but it's a fixed number of steps that has nothing to do with the number of lockers. Case in point, if I gave you not seven but 70 lockers, he could still get lucky and still take just one step. So omega is our lower bound. Big O is our upper bound. Ah, spoiler. What is binary search's lower bound? Well, apparently it's also omega of one, but why? That is in fact correct. Yeah, >> you could just get lucky again. >> Same reason you could get lucky in the best case and it's just smack dab in the middle of all of the data. So the fewest number of steps binary search might take is also actually one. So this is why we talk about upper bound and lower bound because you get kind of a r a sense of the range of performance. Sometimes it's going to be super fast which is great but something tells me in the general case we're not going to get lucky every time we use an algorithm. So it's probably going to be closer to those upper bounds the big O. Now, as an aside, there's a third and final uh symbol that we use in computer science to describe algorithms. That of a capital theta. Capital theta is jargon you can use when big O and omega happen to be the same. And we'll see that today. Not always, but here's a similar cheat sheet. None of the algorithms thus far can be described in this way with theta notation because they are not all the same with their big O and omega. They differed in both of our analyses. But we'll see at least one example of one where it's like okay we can describe this in theta and that's like saying twice as much information with your words to another computer scientist rather than giving them both the upper and the lower bounds. The fancy way of describing all of what we're talking about here big O omega and theta is asmmptoic notation and asmmptoic notation refer or asmmptoic uh lee refers to a value getting bigger and bigger and bigger and bigger but not necessarily ever hitting some boundary as n gets very large in short is what we mean when we deploy this here asmmptoic notation. All right. So, with the first of these things like linear search, let's actually kind of make this a bit more real. Let me actually go over to in just a moment uh my other screen here. Okay. In VS Code, let me go ahead and create a program called search C. And in search C, let's go ahead and implement a fairly simple version of linear search initially. So, let me go ahead and include, for instance, CS50.h. Let me go ahead and include standard io.h. Then, let me go ahead and do in main void. So, we're not going to bother with any command line arguments for now. And then let me go ahead and just give myself an array of numbers to play with. And we did this briefly last week in answer to a question, but I'm going to do it now concretely rather than use something uh ma more manual to get all of these numbers into the array. I'm going to say give me an array called numbers. And the numbers I want to put in this array initially are going to be the exact same denominations we've been playing with. 20 500 10 5 100 1 and 50. Again, this is notation that I alluded to in answer to a question last week whereby if you want to statically initialize an array, that is give it all of your values up front without having the human type them all in manually, you can use curly braces like this. And the compiler is pretty smart. You don't have to bother telling the compiler how many numbers you want, 1 2 3 4 5 6 7 because it can obviously just count how many numbers are in the curly braces, but you could explicitly say seven there so long as your counting is in fact correct. So on line six, this gives me an array of seven numbers initialized to precisely that list of numbers from left to right. All right, let's ask the human now what number they want to search for just as I did our two volunteers and say int n equals get int. Then let's just ask the user for the number that they want to search for. Then let's implement linear search. And if I want to implement linear search in terms of the programming constructs we've seen thus far like what type what uh keyword in C should I use? What programming technique? Yeah. Yeah. So, maybe a for loop or a while loop, but for loop is kind of uh my go-to lately. So, let's do for int i equals 0 because we'll start counting from the left. I is less than seven, which isn't great to hardcode, but I'm not going to use the seven again. So, I think it's okay in one place for this demo. Then, I ++. Then inside of this array, let's go ahead and ask a question just like Jose was by opening each of the doors by saying if numbers bracket i equals equals the number we asked about n, well then let's go ahead and print out some informative message like found back slashn and then for good measure like last week let's return zero to signify success. It's sort of equivalent to returning true but in main recall you have to return an int. That's why we revealed at the end of week two the return type of main is an int because that is what gives the computer its so-called exit status which is zero if all is well or anything other than zero if something went wrong but I think finding the number counts as all is well. But if we get through that whole loop and we still haven't printed found or return zero, I think we can go ahead and safely say not found back slashn and then let's just return one as our exit status to indicate that we didn't find the actual number. So in short, I think this is linear search. Let me open up my terminal window again. Let me make search enter. Let me dot slash search enter. And I'll search for as I asked Jose the number 50. And we indeed found it at the end. Let me go ahead and rerun dot slash search. And let's search for the other number at the beginning 20. That then works. And just to get crazy, let's search for a number we know not to be there like a thousand. And that in fact is not found. So I think we have an implementation then of linear search. But let me pause here and ask if there's any questions with this here code and the translation of algorithm to See yeah in the back why I did not specify the length of the array. So it is not necessary when declaring an array and setting it equal to some known values in advance to specify in the square brackets how many you have because like the compiler is not an idiot. It can literally count the numbers inside of the curly braces and just infer that value. You could put it there, but arguably you're opening up the possibility that you're going to miscount and you're going to put seven here, but eight numbers over there or six numbers there. So, it's best not to attempt fate and just let the compiler do its thing instead. A good question. Other questions on this code so far? All right. If none, let's go ahead and maybe convert this linear search to one that's maybe a little more interesting that involves like searching for strings of text. After all, we started the class in week zero by searching for names in a phone book like John Harvard. Let's see if we can't adapt our code for searching for strings instead of integers. So, in my code here, let's go ahead and delete everything inside of main just to give myself a clean canvas. Let me go ahead and give me another array. This one called, let's just call it strings because that's the goal of this exercise. And set them equal to some familiar pieces from the game of Monopoly if you might have played. So, there's like a battleship piece in there. There's a boot in there. There's a cannon in there, an iron, a thimble, and a top hat, though it does vary nowadays based on the addition that you have. So, kind of a long array, but I have 1 2 3 4 5 six total values in this array of strings. Now, let's ask the user for a string. We'll call it s for short, and say with get string, what string are you looking for among those six? Then I think we can do an a for loop again for int i= 0 i less than 6 i ++ and then inside of this loop let's do the same thing. If uh let's say uh strings bracket i equals equals the string s that the human typed in. I think we can go ahead and say print found back slashn and then as before return zero to signify success and if we don't after that whole for loop let's print at print f not found back slashn down here and return one to signify error. So it's really the same thing at the moment except that I'm actually using strings instead of integers. All right, let me go ahead and open up my terminal window again and clear it. Let me go ahead and recompile this code. Make search.c seems to compile. Okay, let me do dot slash search and let's go ahead and search for the first one. How about battleship enter? Huh, not found. All right. Well, let's maybe I typo maybe. Let me search for something easier to spell. Boot. Not found. That's weird. Both of those are at the very start of the array. Let's do dot slash search again and search for top hat. Enter. Not found. What is going on? Well, this isn't actually that obvious as to what I'm doing wrong. But it turns out that when we actually compare strings instead of integers in C, we're actually going to have to use this other library, at least today, that we saw briefly last week. Last week, we introduced it because of a function called sterling, which gives us the length of a string. Turns out that string.h also comes per its documentation with another useful function called stir comp for string compare. And its purpose in life is to actually compare two strings left and right to make sure they are in fact the same. So for today's purposes, suffice it to say, you cannot use equals equals apparently to compare two strings. Intuitively, why is that? Well, for a computer, it's super easy to compare two integers because they're either there or they're not in memory. But with a string, it's not just a character and another character. It's like seven, a few characters over here and a few characters over here. Maybe it's a few, maybe it's more. You have to compare each and every character in a string to make sure they're in fact the same. So stir compare does exactly that. Probably in the implementation of stir comp from like years ago, someone wrote a while loop or a for loop that looks at each string left to right and compares each and every one of the characters therein and then gives us back an answer. So how do we go about using this? Well, to use stir compare, what I can actually do in VS code here is go and change my code as follows. Instead of using equals equals, I'm going to actually use this function per its documentation. I'm going to call stir compare. Then I'm going to pass in one of the strings which is in strings bracket I. Then I'm going to pass in the second string which is S. However, having read the documentation and this is a little non-obvious. It turns out that stir comp will return zero if the strings are equal. Otherwise, it's going to return a positive number or a negative number. So what I care about for now is does the return value of stir comp when given those two strings give me back zero. If so they are equal and I'm going to say quote unquote found. So let's go ahead and open the terminal again. Let me go ahead and clear it and do make search to recompile my code. And huh I've done something wrong. Let's see. Let me scroll up to the very first line. In line 11, error call to undeclared library function stir comp with type int and something something which gets more complicated after that. Why is line 11 not working despite what I just preached? Yeah. >> Yeah, I just did something stupid. I didn't include the string.h header library. So all clang, our compiler is doing when invoked by make is it's encountering literally the word stir comp and not knowing what it is because we haven't taught it what it is by simply saying include string.h at the top. Okay, let me reopen my terminal window. Clear that message away. Do make search again. Now it's compiling. Dot / search enter. Now I'm going to go ahead and search as I did before for battleship. Ah, now it's finding it. Let me run dot / search again. Search