DAVID MALAN: So let's consider one such algorithm. So on all of our phones, whether iOS or Android or the like, you have some contacts application. And that contacts application's probably storing all of your friends and family members and colleagues, probably alphabetically, maybe by first name, maybe by last name, or however you've organized that device. Well, the old-school version of this happens to be in paper form which looks a little something like this, a phonebook. And inside of an old-school phonebook, really, is that exact same idea. It's much larger. It's much more printed. But it's the same thing. 

There's a whole bunch of names and numbers in a typical phonebook, sorted alphabetically just like your own Android phone or iOS phone might be as well. So suppose we want to solve a problem. And the input to that problem is not only this phone book, but also the name of someone to look up the number for. So my own name, for instance, if I want to look up my phone number or you do, you might open up this book and start looking for David, for instance, if we assume that it's sorted by first name. I don't see David on the first page. So I move on to the second. I don't see myself there. So I move on to the third. I don't see myself there. 

So I move on to the fourth and so forth. One page at a time, looking for my name, and in turn, my number. Well, if correctness is important, let me ask that question first. Is this algorithm, turning the pages step by step, looking for David, correct? What do you think? Within Zoom, you should see some icons under the participant's window labeled Yes and No. If you'd like to go ahead and vote virtually. Yes or no, is this algorithm correct, one page at a time, looking for myself? 

Never mind the fact that this is yellow pages, and so I'm not going to be anywhere in the phone book. But indeed, we'll assume it contains humans as well. All right, so it looks like the algorithm is indeed correct. But it's terribly, terribly slow. And that's OK because one of the ideas we're going to consider in CS50, and in turn, computer science, is not only the correctness of an algorithm, but also the efficiency, how well designed is the algorithm. This is correct. It's just incredibly, incredibly tedious and slow. 

But I will find myself. But, of course, we can do better. Instead of looking for myself one page at a time, why don't I do one page? Let me do 2, 4, 6, 8, 10. It sounds faster. And it is faster. I'm going twice as fast through the phone book, looking for myself. Is this algorithm correct? Let me go to someone in the audience this time. Is this algorithm of searching for someone's name two pages at a time correct? Because I claim it's more efficient. I claim it's better designed because I'll solve the problem twice as fast. Annika? What do you think? 

ANNIKA: No because you might skip your name on the page. 

DAVID: Yeah. I might skip my name on a page. And let me ask a follow up question. Can I fix this? Do I have to throw out the whole algorithm? Or can we at least fix this problem, do you think? 

ANNIKA: I think whatever page you'd flip to, it would help to see what name is there, maybe see if your name would come before or after. 

DAVID: Nice. So that's exactly the right intuition. I don't think we have to completely sacrifice the idea of speeding up this algorithm by moving twice as fast. But as you propose, if I go too far maybe. I get to the E section, which is one letter too late, I should at least double back one page because I could get unlucky. And maybe David is kind of sandwiched in between two pages. At which point, I might fly by, get to the end of the phone book, say, no, there's no David. And I just got unlucky with, like, 50% probability. But, as you propose, I can at least recover and sort of conditionally ask myself, wait a minute, maybe I just missed it and double back. 

So I can get the overall speed improvement but then at least fix that kind of mistake or bug. And bug, a term of art in programming, a bug is just a mistake in a program or a mistake, more generally, in an algorithm. But honestly, none of us are going to do that. When we actually go to search for someone in a phone book, just like our phones do, they typically don't start at the top and go to the bottom. And computers do exactly what you might do more intuitively. They'll probably go roughly to the middle. Maybe they'll skew a little to the left if you know D is toward the start of an alphabet. But, no, I open to the middle sort of sloppily. And I'm in the M section. 

So what do I know when I'm in the M section about this problem? Let me call on one more person. I'm in the M section. What would you do as a human now, taking this as input to solve this problem? What do I know about the location, of course, my name in the phone book? What decision can I make here? What decision can I make? Kyle, what do you think? 

KYLE: Yeah. So from the M onwards, you know that your name won't be there for sure. 

DAVID: Yeah. So my name is not going to be in the M section. But thanks to the alphabetized portion of the phone book, I at least know, you know what? I can take a huge bite out of this problem and tear the problem in half, both metaphorically and also literally in the case of a phone book. And I can literally throw half of the problem away. And so if I started with some, like, 1,000 pages in this phone book or 1,000 contacts in my phone, just by going to the middle roughly and taking a look to the left and the right, I can decide, as you note, well, it's not on the page I'm looking for. But I can decide it's to the left or to the right. 

I know D comes before M. And so now I can go to the left. And you know what's interesting here is that I can use that exact same algorithm. I don't have to think any differently. I can apply the same logic, open to the middle of this half of the phonebook, and now I see I'm in the G section. So I'm still a little too far. But, again, I can tear half the problem away, throw it down. And now I've gone from 1,000 pages to 500 pages to 250 pages. If I do this again, I might find myself, oh, I made it to the C section now. 

I can tear the problem in half again, throw the left half away, and now I'm down to just 125 pages. Now, that's still a lot. But, my God, I've gone from 1,000 to 500 to 250, to 125. That is way faster than going from 1,000 to 999 to 998. And it's even faster than going from 1,000 to 998, to 996, to 994. Both of those algorithms are going to take me much longer as well.