## 字幕表 動画を再生する

• So what might an algorithm be for a problem that we might want to solve?

• Well, consider this.

• This is an old school problem where you might have lots and lots of names and lots of knots of numbers.

• And those names air hopefully sorted alphabetically from a through Z in a book like this.

• And even though most of us don't really reach for this technology anymore, consider that it's really the same as your iPhone or Android phone or other device, which has all of your contacts top to bottom, and you can scroll through them from A to Z.

• Or you can search for them by typing into the little auto complete box.

• How is even your phone solving this problem?

• Well, let's consider a simple approach.

• I'm gonna look at the first page and look for someone on the phone book.

• Supposed.

• That person's name is Mike Smith.

• Last name Starting with s.

• Let me go ahead and look down.

• He's not here.

• Let me turn the page.

• Let me turn the page.

• Let me turn the page.

• This is an algorithm.

• It's a step by step process for solving a problem.

• Finding Mike Smith is this algorithm correct?

• Would you say Yeah, I mean, it's pretty slow.

• It's pretty stupid in that it's gonna take my God forever, like hundreds of page turns, to find Mike Smith.

• But if he's there, I will find him according to this step by step approach.

• What if I speed things up a bit just because it's tedious?

• Otherwise, So I do.

• 2468 10 12 14 16 and so forth.

• Is that algorithm faster?

• Absolutely, literally, twice as fast.

• Is it correct?

• No.

• Why?

• Yeah, we might skip it.

• I might get unlucky.

• And eventually I might get to like the esses.

• But darn it, if Mike wasn't in between two pages as I turned them at once.

• So it's not a fatal flaw, that algorithm I could fix by just saying if you hit the T section or maybe s n instead of S m, just back up one or so pages just to fix that bug or mistakes, so to speak.

• But the beast is twice as fast.

• But if this phone book has like 1000 something pages, it's still gonna take me.

• Maybe like 500 pair wise turns just defined Mike Smith.

• That's a while just to look someone up.

• But most of us, if you've used this technology instead, did what back in the day, go like roughly to the middle, right?

• If there aren't little letters on the side of which the cheat so well, roughly into the middle I'm in the M section now.

• The EMS off course mean that Mike is not this way, which would be the A's.

• He's probably this way toward disease, because s, of course, is between the M and the sea.

• So at this point, I can literally tear the problem in half, throw half of the problem away very dramatically and unnecessarily making the point that we've now gone from 1000 some odd pages to what 500.

• And I could do it again.

• I went a little too far now in the tea section so I could tear the problem in half again.

• Throw that half away and now I'm down to from 1000 to 500 to 250 pages on Lee after just two steps in this step by step process.

• And if I repeat this again and again and again, hopefully I'll be left ultimately with, say, just one page on which Mike Smith either is or is not, and I can call him or quits.

So what might an algorithm be for a problem that we might want to solve?

A2 初級

# CS50 2019 - 再生0 - バイナリ検索 (CS50 2019 - Lecture 0 - Binary Search)

• 0 0
林宜悉 に公開 2021 年 01 月 14 日