1
00:00:00,000 --> 00:00:06,370

2
00:00:06,370 --> 00:00:08,150
>> JASON HIRSCHHORN: Welcome
to week three, everyone.

3
00:00:08,150 --> 00:00:11,650
We have a busy but exciting
section ahead of us.

4
00:00:11,650 --> 00:00:17,010
So first, because we have made some
headway with the course but we still

5
00:00:17,010 --> 00:00:20,570
have a lot of learning left to do, I'm
going to show you guys some resources

6
00:00:20,570 --> 00:00:24,160
that should prove to be incredibly
helpful as you not only approach your

7
00:00:24,160 --> 00:00:28,130
problem sets, but also digest all of
the material we give you guys in

8
00:00:28,130 --> 00:00:30,800
lectures and shorts and section.

9
00:00:30,800 --> 00:00:34,790
>> Then we're going to spend the first 20
to 25 minutes of section going over

10
00:00:34,790 --> 00:00:38,630
GDB, which you may or may not have
used at this point, but it is an

11
00:00:38,630 --> 00:00:42,570
incredibly helpful tool that will
help you debug your programs.

12
00:00:42,570 --> 00:00:46,060
A lot of you may have used printf in the
middle of your program to figure

13
00:00:46,060 --> 00:00:47,430
out what a variable equaled.

14
00:00:47,430 --> 00:00:52,060
GDB is even better than printf and
doesn't screw up your code because you

15
00:00:52,060 --> 00:00:53,320
run it on an executable file.

16
00:00:53,320 --> 00:00:56,500
So we'll go over the 10 most helpful
commands you need for GDB, and we're

17
00:00:56,500 --> 00:01:00,540
going to go on an exercise together so
in problem set three and beyond, you

18
00:01:00,540 --> 00:01:03,320
can use GDB to help debug
your programs.

19
00:01:03,320 --> 00:01:06,420
And finally, we're going to go over some
sorting and searching algorithms

20
00:01:06,420 --> 00:01:10,590
that you saw in lecture, and we are
going to actually code, not just

21
00:01:10,590 --> 00:01:17,360
pseudocode, but code binary search,
bubble sort, and selection sort.

22
00:01:17,360 --> 00:01:20,090
>> So first, I want to go
over the resources.

23
00:01:20,090 --> 00:01:23,530
This is an extensive list, and it's
smaller font because I had a lot to

24
00:01:23,530 --> 00:01:24,390
fit on here.

25
00:01:24,390 --> 00:01:26,950
But these will not only help you,
again, with the problem sets and

26
00:01:26,950 --> 00:01:30,760
digesting information you learned, but
definitely, come quiz time, these will

27
00:01:30,760 --> 00:01:32,130
be incredibly helpful.

28
00:01:32,130 --> 00:01:34,700
So first, the lecture notes.

29
00:01:34,700 --> 00:01:39,480
If you go to cs50.net/lectures and
scroll to the specific week and day,

30
00:01:39,480 --> 00:01:43,120
you'll see that there are notes for each
lecture, which is not simply a

31
00:01:43,120 --> 00:01:47,250
transcript, but an edited version of
what was covered in lecture with code

32
00:01:47,250 --> 00:01:49,610
snippets and other helpful tidbits.

33
00:01:49,610 --> 00:01:52,220
I highly recommend going over those.

34
00:01:52,220 --> 00:01:55,340
And then as well, there's source code
available from each lecture.

35
00:01:55,340 --> 00:02:00,050
And again, these slides will also be
available online at cs50.net/sections

36
00:02:00,050 --> 00:02:01,480
this evening.

37
00:02:01,480 --> 00:02:06,860
>> So second are the shorts each week that
cover topics, usually 5 to 15

38
00:02:06,860 --> 00:02:08,090
minutes in length.

39
00:02:08,090 --> 00:02:12,310
And those hopefully will give you a
great primer on different topics.

40
00:02:12,310 --> 00:02:12,870
Third--

41
00:02:12,870 --> 00:02:16,370
and this is brand new this
year-- is study.cs50.net.

42
00:02:16,370 --> 00:02:20,110
If you have not checked it out, I
highly recommend that you do so.

43
00:02:20,110 --> 00:02:21,100
You get to pick a topic.

44
00:02:21,100 --> 00:02:23,040
We have dozens of topics on there.

45
00:02:23,040 --> 00:02:24,770
So for example, you pick Functions.

46
00:02:24,770 --> 00:02:27,270
It gives you some slides
and notes on functions.

47
00:02:27,270 --> 00:02:31,190
Those are actually the slides that TFs
are encouraged to use during our

48
00:02:31,190 --> 00:02:32,710
presentations in section.

49
00:02:32,710 --> 00:02:35,040
There's also tips and tricks for dealing
with functions, and there's

50
00:02:35,040 --> 00:02:37,290
practice problems that help
you work with functions.

51
00:02:37,290 --> 00:02:41,500
We also give you links to the short on
functions and the times that functions

52
00:02:41,500 --> 00:02:42,750
have come up in lecture.

53
00:02:42,750 --> 00:02:46,550
So study.cs50.net, brand new this
year, a fantastic resource.

54
00:02:46,550 --> 00:02:52,180
>> Next, I have man, which is the manual
command that you can run at the

55
00:02:52,180 --> 00:02:52,770
command line.

56
00:02:52,770 --> 00:02:57,880
So if you have any questions about a
command, for example, rand, which we

57
00:02:57,880 --> 00:03:00,900
encountered last week during section
and you have likely encountered in

58
00:03:00,900 --> 00:03:05,380
your problem set when going through the
generate code, but if you type man

59
00:03:05,380 --> 00:03:09,980
rand, you'll get the page that
tells you all about rand.

60
00:03:09,980 --> 00:03:14,040
It gives you what it takes, the
parameters it takes, as well as return

61
00:03:14,040 --> 00:03:16,530
type and a brief description
of that function.

62
00:03:16,530 --> 00:03:17,500
>> So check out rand.

63
00:03:17,500 --> 00:03:22,270
It can be a little wordy and confusing,
so sometimes I find that

64
00:03:22,270 --> 00:03:26,150
simply Googling what I want to know is
the best way to find the answer.

65
00:03:26,150 --> 00:03:27,940
So practice with Google.

66
00:03:27,940 --> 00:03:28,600
Get good at Google.

67
00:03:28,600 --> 00:03:30,600
It will become your best friend.

68
00:03:30,600 --> 00:03:34,300
>> As well as Google, if you can't find it
on Google, cs50.net/discuss, it's

69
00:03:34,300 --> 00:03:35,550
the discussion forum.

70
00:03:35,550 --> 00:03:39,390
Chances are if you have a question, one
of your 700+ peers also has that

71
00:03:39,390 --> 00:03:42,110
question and may have asked
it already in the discuss

72
00:03:42,110 --> 00:03:43,540
forums and have it answered.

73
00:03:43,540 --> 00:03:48,130
So if you have a common question or
you have a question that you think

74
00:03:48,130 --> 00:03:52,300
maybe other people might have run into,
check out cs50.net/discuss.

75
00:03:52,300 --> 00:03:55,450
>> Finally, the last two, if you want to
talk to a real human being, office

76
00:03:55,450 --> 00:03:57,770
hours Monday through Friday.

77
00:03:57,770 --> 00:04:00,850
There's also online office hours
for extension students.

78
00:04:00,850 --> 00:04:04,370
And last but certainly not least,
me, exclamation point.

79
00:04:04,370 --> 00:04:05,960
You all have my contact information.

80
00:04:05,960 --> 00:04:11,940
If you need anything, please never
hesitate to contact me.

81
00:04:11,940 --> 00:04:14,020
Always feel free to do so.

82
00:04:14,020 --> 00:04:17,490
Very few of you have added me on Gchat,
so that has been disappointing,

83
00:04:17,490 --> 00:04:20,410
but hopefully that'll change between
this and next section.

84
00:04:20,410 --> 00:04:22,105
Any questions so far on the resources?

85
00:04:22,105 --> 00:04:25,670

86
00:04:25,670 --> 00:04:27,450
Great.

87
00:04:27,450 --> 00:04:34,280
>> Finally, another plug for
feedback, sayat.me/cs50.

88
00:04:34,280 --> 00:04:37,050
You can give me anonymous feedback
on how I'm doing.

89
00:04:37,050 --> 00:04:38,320
That was really helpful last week.

90
00:04:38,320 --> 00:04:41,890
I got a couple of comments from you guys
right after section, plus from

91
00:04:41,890 --> 00:04:44,750
other students who watched it
during the week, and it

92
00:04:44,750 --> 00:04:46,830
was incredibly helpful.

93
00:04:46,830 --> 00:04:50,250
I am going to try and limit my use of
the word "sweet," but I will show my

94
00:04:50,250 --> 00:04:52,410
enthusiasm and excitement
in other ways.

95
00:04:52,410 --> 00:04:56,550
But there were other additional
substantive feedbacks,

96
00:04:56,550 --> 00:04:57,600
both pluses and delta.

97
00:04:57,600 --> 00:05:00,480
So please, I give you guys feedback
on your problem sets.

98
00:05:00,480 --> 00:05:01,790
Feel free to give me feedback
on my teaching.

99
00:05:01,790 --> 00:05:04,010
I'm here for you guys.

100
00:05:04,010 --> 00:05:05,270
>> Great.

101
00:05:05,270 --> 00:05:07,020
That is all I have for
the first section.

102
00:05:07,020 --> 00:05:08,565
Does anybody have any
questions so far?

103
00:05:08,565 --> 00:05:12,370

104
00:05:12,370 --> 00:05:14,640
And I have a note for
the control center.

105
00:05:14,640 --> 00:05:21,200
Extension students have messaged me
saying they're not getting any audio,

106
00:05:21,200 --> 00:05:23,870
but that is out of my power to fix.

107
00:05:23,870 --> 00:05:25,280
So hopefully, that gets
resolved shortly.

108
00:05:25,280 --> 00:05:28,850
If you're watching online, hi,
but you can't hear me.

109
00:05:28,850 --> 00:05:33,860
>> So first, we are going
to go through GDB.

110
00:05:33,860 --> 00:05:37,100
GDB, as I hinted at earlier,
is a debugging tool

111
00:05:37,100 --> 00:05:39,040
much better than printf.

112
00:05:39,040 --> 00:05:44,700
So to get started with GDB, you guys, if
you want to open up your appliance

113
00:05:44,700 --> 00:05:49,070
and take the file that I emailed to you
earlier-- this file will also be

114
00:05:49,070 --> 00:05:51,940
available online in a bit--

115
00:05:51,940 --> 00:05:55,700
and run GDB./ the name of the file.

116
00:05:55,700 --> 00:05:58,580
First, of course, you have to compile
file because GDB only works on

117
00:05:58,580 --> 00:05:59,890
executable files.

118
00:05:59,890 --> 00:06:02,300
>> But if you ever want to start
GDB, the first thing you do,

119
00:06:02,300 --> 00:06:04,550
you run GDB./ Caesar.

120
00:06:04,550 --> 00:06:08,340
So that's the name of the program we're
going to go with it right now.

121
00:06:08,340 --> 00:06:12,810
So I'm going to write make Caesar, which
will give me an executable file

122
00:06:12,810 --> 00:06:14,100
here highlighted in green.

123
00:06:14,100 --> 00:06:19,250
And then I'm going to run GDB./ Cesar.

124
00:06:19,250 --> 00:06:19,810
>> And there you go.

125
00:06:19,810 --> 00:06:24,540
You see we have some text telling me
about the version of GDB, giving me

126
00:06:24,540 --> 00:06:27,570
some warranty information, and then we
have the GDP prompt, which looks sort

127
00:06:27,570 --> 00:06:29,350
of like our command line prompt,
but you see it's open

128
00:06:29,350 --> 00:06:32,510
paren, GDB, close paren.

129
00:06:32,510 --> 00:06:36,520
Before we continue and debug this file
that I sent to you all, let's look at

130
00:06:36,520 --> 00:06:40,220
some useful commands so we have a sense
of what we are going to cover.

131
00:06:40,220 --> 00:06:45,060
>> These commands are listed here in the
order in which I generally use them.

132
00:06:45,060 --> 00:06:50,230
So I start my program by running
GBD./ name of the program,

133
00:06:50,230 --> 00:06:51,360
in this case, Caesar.

134
00:06:51,360 --> 00:06:57,430
And then the first thing I do 99.9%
of the time is type break mean.

135
00:06:57,430 --> 00:06:59,070
That sets a break point at main.

136
00:06:59,070 --> 00:07:03,260
Essentially, what you're doing there
is the program is going to stop at

137
00:07:03,260 --> 00:07:06,100
main so you can start examining it line
by line, rather than running all

138
00:07:06,100 --> 00:07:07,040
the way through.

139
00:07:07,040 --> 00:07:09,730
You can break at different points in
your code, but main is generally a

140
00:07:09,730 --> 00:07:11,870
good place to start.

141
00:07:11,870 --> 00:07:14,840
>> The next command I run is run.

142
00:07:14,840 --> 00:07:17,400
That starts the program running, and
if you need to enter command line

143
00:07:17,400 --> 00:07:19,090
arguments, you run it that command.

144
00:07:19,090 --> 00:07:20,500
Run with the arguments.

145
00:07:20,500 --> 00:07:25,000
So since we are going over a version
of C, which is the program you guys

146
00:07:25,000 --> 00:07:26,160
wrote for pset two--

147
00:07:26,160 --> 00:07:29,880
this one, of course, has some bugs
in it that hopefully we'll find--

148
00:07:29,880 --> 00:07:32,810
we're going to run run with some command
line arguments because Caesar,

149
00:07:32,810 --> 00:07:34,860
as you guys know per the problem
set spec, takes some

150
00:07:34,860 --> 00:07:36,380
command line arguments.

151
00:07:36,380 --> 00:07:40,000
>> The next couple of commands, the next
one is actually called next.

152
00:07:40,000 --> 00:07:42,470
That one takes you line by line
through your program.

153
00:07:42,470 --> 00:07:45,800
So hitting n then Enter takes you
to the next line, executing

154
00:07:45,800 --> 00:07:46,880
the previous line.

155
00:07:46,880 --> 00:07:49,440
Step not only takes you to
the next line, but it

156
00:07:49,440 --> 00:07:51,070
takes you inside functions.

157
00:07:51,070 --> 00:07:54,310
So if you have written a function in
your code or if you want to explore a

158
00:07:54,310 --> 00:07:57,820
to i, for example, you can hit s, and
rather than going to the next line of

159
00:07:57,820 --> 00:08:02,390
the file that you're going through right
now, you'll actually step into

160
00:08:02,390 --> 00:08:04,670
this function and see its code.

161
00:08:04,670 --> 00:08:12,300
>> List shows you, in very user friendly
format, the 10 or so lines around

162
00:08:12,300 --> 00:08:14,940
where you currently are in your code
so you can actually see the file

163
00:08:14,940 --> 00:08:17,810
rather than having to swap back and
forth between different views.

164
00:08:17,810 --> 00:08:21,890
Print is like printf,
as its name implies.

165
00:08:21,890 --> 00:08:24,020
That shows you what a variable equals.

166
00:08:24,020 --> 00:08:25,870
>> Info locals is really helpful.

167
00:08:25,870 --> 00:08:27,740
This is a special version of print.

168
00:08:27,740 --> 00:08:31,770
Info locals shows you all of the local
variables, prints them all out for you

169
00:08:31,770 --> 00:08:33,380
that are currently available.

170
00:08:33,380 --> 00:08:36,360
So I generally, rather than having to
print out the four variables that I'm

171
00:08:36,360 --> 00:08:39,929
curious about if I'm in a for loop, for
example, I just write info locals,

172
00:08:39,929 --> 00:08:43,470
and it'll show me what my counter i
equals, as well as the array that I'm

173
00:08:43,470 --> 00:08:45,130
working on equals.

174
00:08:45,130 --> 00:08:47,530
>> Finally, continue.

175
00:08:47,530 --> 00:08:49,300
Typing break stops you
at the break point.

176
00:08:49,300 --> 00:08:51,380
You can walk through line by
line with next and step.

177
00:08:51,380 --> 00:08:55,640
Continue runs the program to your next
break point or until completion if

178
00:08:55,640 --> 00:08:57,180
there are no more break points.

179
00:08:57,180 --> 00:09:00,060
Disable removes break points if you
decided the break at main was

180
00:09:00,060 --> 00:09:01,890
inappropriate, you want to
set it somewhere else.

181
00:09:01,890 --> 00:09:05,090
And finally q, quit, gets out of GDB.

182
00:09:05,090 --> 00:09:10,784
>> So this program, ./ Caesar, we are going
to look through right now and we

183
00:09:10,784 --> 00:09:13,490
are going to use GDB to find
the bugs in this program.

184
00:09:13,490 --> 00:09:18,110
I ran this program earlier with
Check 50, and I got one frown.

185
00:09:18,110 --> 00:09:22,310
Everything it existed, it compiled, it
passed a lot of the tests, but for

186
00:09:22,310 --> 00:09:27,950
some reason, it did not pass the fifth
test, turning BARFOO, all caps, into

187
00:09:27,950 --> 00:09:33,350
E-D-U-I-R-R, all caps,
using three as a key.

188
00:09:33,350 --> 00:09:34,090
I got pretty close.

189
00:09:34,090 --> 00:09:35,410
I got off by one letter.

190
00:09:35,410 --> 00:09:37,340
So there's some small mistake in here.

191
00:09:37,340 --> 00:09:38,070
I've looked through my code.

192
00:09:38,070 --> 00:09:38,850
I couldn't figure it out.

193
00:09:38,850 --> 00:09:41,740
Hopefully, you guys can help me
figure out what this bug is.

194
00:09:41,740 --> 00:09:44,610
>> So that's the error we're
searching for.

195
00:09:44,610 --> 00:09:46,090
Let's move into GDB.

196
00:09:46,090 --> 00:09:51,100
Again, I've run GDB ./ Caesar,
so now we're in GDB.

197
00:09:51,100 --> 00:09:54,290
And what is the first
thing I should do?

198
00:09:54,290 --> 00:09:56,680
I've just entered GDB.

199
00:09:56,680 --> 00:10:00,316
Somebody give me a good
command to enter.

200
00:10:00,316 --> 00:10:01,140
>> STUDENT: Break main.

201
00:10:01,140 --> 00:10:01,800
>> JASON HIRSCHHORN: Break main.

202
00:10:01,800 --> 00:10:02,900
Fantastic.

203
00:10:02,900 --> 00:10:03,560
Let's type that in.

204
00:10:03,560 --> 00:10:06,390
You guys can watch up here or follow
along on your computers.

205
00:10:06,390 --> 00:10:09,410
Break main, and you'll see a
break point was set at--

206
00:10:09,410 --> 00:10:12,340
it gives me some weird memory address,
and it also gives me the line number.

207
00:10:12,340 --> 00:10:15,310
If I were to look back at this file,
I would realize that main

208
00:10:15,310 --> 00:10:17,700
happened on line 21.

209
00:10:17,700 --> 00:10:18,950
What should I run next?

210
00:10:18,950 --> 00:10:22,970

211
00:10:22,970 --> 00:10:25,060
Is my program running?

212
00:10:25,060 --> 00:10:25,650
No.

213
00:10:25,650 --> 00:10:27,175
So what should I run next?

214
00:10:27,175 --> 00:10:27,520
>> STUDENT: Run.

215
00:10:27,520 --> 00:10:28,050
>> JASON HIRSCHHORN: Run.

216
00:10:28,050 --> 00:10:30,760
Should I just run run, or should
I add some other things in?

217
00:10:30,760 --> 00:10:31,960
>> STUDENT: Run with the argument.

218
00:10:31,960 --> 00:10:33,320
>> JASON HIRSCHHORN: Run with
the command arguments.

219
00:10:33,320 --> 00:10:36,420
And since I'm debugging a very specific
case, I should enter that

220
00:10:36,420 --> 00:10:37,120
command line argument.

221
00:10:37,120 --> 00:10:42,290
So I'll do run three, which is, again,
the output I got from Check 50.

222
00:10:42,290 --> 00:10:44,240
Starting program.

223
00:10:44,240 --> 00:10:45,420
We go through a couple of lines.

224
00:10:45,420 --> 00:10:47,700
You'll now see that we're on line 21.

225
00:10:47,700 --> 00:10:49,200
How do I know that we're on line 21?

226
00:10:49,200 --> 00:10:52,170
Because if you look to the left
of my terminal window, there

227
00:10:52,170 --> 00:10:53,120
it says line 21.

228
00:10:53,120 --> 00:10:57,010
And that gives me, actually, the
code that is at line 21.

229
00:10:57,010 --> 00:10:58,440
So I misspoke earlier.

230
00:10:58,440 --> 00:10:59,770
Main is not actually at line 21.

231
00:10:59,770 --> 00:11:02,000
Main is a couple of lines above 21.

232
00:11:02,000 --> 00:11:04,300
But at line 21, that's
where we're breaking.

233
00:11:04,300 --> 00:11:06,280
This line of code has
not yet executed.

234
00:11:06,280 --> 00:11:06,890
That's important.

235
00:11:06,890 --> 00:11:09,120
The line you see has not
been executed yet.

236
00:11:09,120 --> 00:11:12,650
That's the next line of code
you're about to execute.

237
00:11:12,650 --> 00:11:15,860
>> So the next line, as you guys are
probably familiar with, is this

238
00:11:15,860 --> 00:11:20,070
condition checking to see if I have
entered a command line argument.

239
00:11:20,070 --> 00:11:22,140
And a to i, what is the second
part of that doing?

240
00:11:22,140 --> 00:11:23,457
What is a to i?

241
00:11:23,457 --> 00:11:24,950
>> STUDENT: Changing it to an integer.

242
00:11:24,950 --> 00:11:25,450
>> JASON HIRSCHHORN: Sorry?

243
00:11:25,450 --> 00:11:27,400
>> STUDENT: It's changing the
argument to an integer.

244
00:11:27,400 --> 00:11:30,890
>> JASON HIRSCHHORN: So a to i changes arg
v1 from a string to an integer.

245
00:11:30,890 --> 00:11:32,140
And then what's it checking?

246
00:11:32,140 --> 00:11:35,414

247
00:11:35,414 --> 00:11:37,112
>> STUDENT: If there is a second
command line argument, aside

248
00:11:37,112 --> 00:11:38,100
from running the program.

249
00:11:38,100 --> 00:11:39,460
>> JASON HIRSCHHORN: And what's
the second half of this

250
00:11:39,460 --> 00:11:41,220
Boolean expression checking?

251
00:11:41,220 --> 00:11:42,540
This part over here, a to i?

252
00:11:42,540 --> 00:11:44,080
>> STUDENT: If it's negative.

253
00:11:44,080 --> 00:11:45,380
>> JASON HIRSCHHORN: Making sure what?

254
00:11:45,380 --> 00:11:47,120
>> STUDENT: Making sure it
is, in fact, positive.

255
00:11:47,120 --> 00:11:47,650
>> JASON HIRSCHHORN: Exactly.

256
00:11:47,650 --> 00:11:50,600
This is checking to see if it's
negative, and if it is negative, I

257
00:11:50,600 --> 00:11:53,220
have a feeling the next line might
be me yelling at the user.

258
00:11:53,220 --> 00:11:55,930
So let's hit end to execute this line.

259
00:11:55,930 --> 00:11:59,925
We don't see that line that you guys
maybe expected to see yelling at the

260
00:11:59,925 --> 00:12:03,030
user and then returning, because
this line did not execute.

261
00:12:03,030 --> 00:12:03,840
I entered 3.

262
00:12:03,840 --> 00:12:06,860
So I did, in fact, enter two command
line arguments, and 3 is

263
00:12:06,860 --> 00:12:07,610
greater than zero.

264
00:12:07,610 --> 00:12:09,950
So we saw that line, we executed,
but we did not step

265
00:12:09,950 --> 00:12:11,300
inside the if condition.

266
00:12:11,300 --> 00:12:17,060
>> So now, next, I see I'm setting
int key equals a to i arg v1.

267
00:12:17,060 --> 00:12:18,840
So that is me creating a variable key.

268
00:12:18,840 --> 00:12:22,450
So if I print out key right now, because
that allows you to see the

269
00:12:22,450 --> 00:12:26,040
value inside the variable,
key equals 47.

270
00:12:26,040 --> 00:12:28,810
That's weird, but of course,
that's because I haven't

271
00:12:28,810 --> 00:12:30,490
executed that line yet.

272
00:12:30,490 --> 00:12:35,880
So now if I hit n, execute that line,
and do print key, key will equal 3,

273
00:12:35,880 --> 00:12:37,740
which is what we expect it to equal.

274
00:12:37,740 --> 00:12:41,170
>> So again, in GDB, the line you
see you haven't executed yet.

275
00:12:41,170 --> 00:12:44,850
You have to hit n or s or a number
of other commands to actually

276
00:12:44,850 --> 00:12:46,610
execute that line.

277
00:12:46,610 --> 00:12:47,380
Print key.

278
00:12:47,380 --> 00:12:48,280
Key's at 3.

279
00:12:48,280 --> 00:12:49,750
So far, so good.

280
00:12:49,750 --> 00:12:51,000
String is plain text.

281
00:12:51,000 --> 00:12:52,270
Let's execute that line.

282
00:12:52,270 --> 00:12:53,970
I'm getting a string from user.

283
00:12:53,970 --> 00:12:58,690
>> Let's see in my Check 50, I
enter BARFOO all caps, so

284
00:12:58,690 --> 00:13:01,330
that's what I'll enter.

285
00:13:01,330 --> 00:13:07,300
If I now print plain text.

286
00:13:07,300 --> 00:13:08,610
You'll see it equals a string.

287
00:13:08,610 --> 00:13:11,100
It gives me some other weird hexadecimal
number, but it does in

288
00:13:11,100 --> 00:13:13,620
fact say that my string is BARFOO.

289
00:13:13,620 --> 00:13:19,308
If I wanted to see what key equaled at
this point, how could I check key?

290
00:13:19,308 --> 00:13:20,710
>> STUDENT: Print key.

291
00:13:20,710 --> 00:13:22,010
>> JASON HIRSCHHORN: Print key, exactly.

292
00:13:22,010 --> 00:13:23,260
And actually, there's a shortcut.

293
00:13:23,260 --> 00:13:25,910
If you get tired of typing print,
you can just type p.

294
00:13:25,910 --> 00:13:28,340
So p key does the same exact thing.

295
00:13:28,340 --> 00:13:29,730
And again, I see it equals 3.

296
00:13:29,730 --> 00:13:34,760
>> If I wanted to find out what both key
and BARFOO equaled at the same time

297
00:13:34,760 --> 00:13:37,215
but I was tired of typing each
one out individually, I

298
00:13:37,215 --> 00:13:38,590
could type info locals.

299
00:13:38,590 --> 00:13:41,170
That gives me key equals 3.

300
00:13:41,170 --> 00:13:42,500
Plain text equals BARFOO.

301
00:13:42,500 --> 00:13:45,265
It also gives me these two weird things
at the top, this variable i and

302
00:13:45,265 --> 00:13:46,590
this variable n.

303
00:13:46,590 --> 00:13:48,460
>> Those are actually existing
in my main program.

304
00:13:48,460 --> 00:13:51,280
We haven't encountered them yet,
but as a preview, those

305
00:13:51,280 --> 00:13:52,880
exist in my for loop.

306
00:13:52,880 --> 00:13:55,360
So right now, they equal some weird
numbers because they haven't been

307
00:13:55,360 --> 00:13:58,300
initialized yet, but they do still exist
in memory, so they're just set

308
00:13:58,300 --> 00:14:00,220
to some garbage value.

309
00:14:00,220 --> 00:14:02,890
But we do see key in plain
text right there.

310
00:14:02,890 --> 00:14:06,390
>> So I'm going to execute this line,
line 34, the for loop.

311
00:14:06,390 --> 00:14:08,220
We're going to jump into the
for loop by hitting n.

312
00:14:08,220 --> 00:14:10,050
And we're inside the for loop.

313
00:14:10,050 --> 00:14:11,360
We're at our first check.

314
00:14:11,360 --> 00:14:14,300
And again, these should sort of look
familiar to you because this was a

315
00:14:14,300 --> 00:14:18,080
Caesar program that was written, but
again, has some sort of bug.

316
00:14:18,080 --> 00:14:21,940
>> And now if I do info locals, because I'm
inside that for loop, you'll see

317
00:14:21,940 --> 00:14:23,900
that i equals zero, as we expect.

318
00:14:23,900 --> 00:14:26,820
That's what we set it to and initialized
it to in the for loop.

319
00:14:26,820 --> 00:14:27,560
n equals 6.

320
00:14:27,560 --> 00:14:30,700
That also makes sense because we set
it to the strlen of plain text.

321
00:14:30,700 --> 00:14:34,270
So I like to do info locals or print
to variable often to make sure that

322
00:14:34,270 --> 00:14:36,370
everything is always what
I expect it to equal.

323
00:14:36,370 --> 00:14:39,800
In this case, everything is
what I expect it to equal.

324
00:14:39,800 --> 00:14:41,850
>> So let's start moving through
this for loop.

325
00:14:41,850 --> 00:14:45,715
The line I'm on is line 36, if plain
text i is greater than a and plain

326
00:14:45,715 --> 00:14:48,540
text i is less than or equal to z.

327
00:14:48,540 --> 00:14:51,880
I know my problem is not with my first
letter, it's with the second letter.

328
00:14:51,880 --> 00:14:56,290
If we look back at Check
50, B goes to E fine.

329
00:14:56,290 --> 00:14:59,010
I'm taking the A and leaving it as
an A, not changing it to D. So

330
00:14:59,010 --> 00:15:00,200
something's wrong with
the second letter.

331
00:15:00,200 --> 00:15:01,640
So I'm going to move
there in a second.

332
00:15:01,640 --> 00:15:06,030
>> But if I did want to check what plain
text I equaled in this particular

333
00:15:06,030 --> 00:15:07,760
case, I think it should be what?

334
00:15:07,760 --> 00:15:10,980
What should plain text I equal in this
first round through the for loop?

335
00:15:10,980 --> 00:15:14,046

336
00:15:14,046 --> 00:15:15,110
>> STUDENT: Zero?

337
00:15:15,110 --> 00:15:16,510
>> JASON HIRSCHHORN: Plain text of I?

338
00:15:16,510 --> 00:15:21,180
So it should be capital B. I, of course,
equals zero, but plain text

339
00:15:21,180 --> 00:15:25,600
bracket zero closed bracket equals B
because strings, as we saw last week,

340
00:15:25,600 --> 00:15:28,650
are array, so we're getting the
first character from that.

341
00:15:28,650 --> 00:15:34,960
So again, if I printed out plain text of
I, I do, in fact, get the character

342
00:15:34,960 --> 00:15:36,560
B. And that's neat, right?

343
00:15:36,560 --> 00:15:40,380
I don't actually have plain text I.
That's not one of the variables I set

344
00:15:40,380 --> 00:15:42,950
or initialized, but you can print
out a whole host of things

345
00:15:42,950 --> 00:15:45,640
if you'd like to.

346
00:15:45,640 --> 00:15:47,340
>> But let's move through.

347
00:15:47,340 --> 00:15:50,050
If plain text I is greater than A and
plain text I is less than or equal to

348
00:15:50,050 --> 00:15:53,290
Z, that clearly is true because we have
a capital B. I'm going to run

349
00:15:53,290 --> 00:15:54,230
some command on it.

350
00:15:54,230 --> 00:15:58,530
We saw that math last week, so we'll
take it for granted that it works

351
00:15:58,530 --> 00:16:00,900
right according to Check 50.

352
00:16:00,900 --> 00:16:03,720
>> These curly braces, the first one
showed that I was exiting the if

353
00:16:03,720 --> 00:16:07,030
condition, the second one showed
that I'm exiting the for loop.

354
00:16:07,030 --> 00:16:10,400
And so now when I hit Next, we'll see
we're back at the for loop again.

355
00:16:10,400 --> 00:16:11,970
We're going through the
for loop again.

356
00:16:11,970 --> 00:16:18,110
Let's actually step into the second
iteration of the for loop and type

357
00:16:18,110 --> 00:16:20,520
info locals.

358
00:16:20,520 --> 00:16:22,190
>> So we're in the second iteration
of our for loop.

359
00:16:22,190 --> 00:16:24,530
I equals 1, which we expect.

360
00:16:24,530 --> 00:16:26,650
N equals 6, which we expect.

361
00:16:26,650 --> 00:16:28,810
Key equals 3, which we expect.

362
00:16:28,810 --> 00:16:32,625
And plain text, you'll see, equals
EARFOO now, not BARFOO anymore because

363
00:16:32,625 --> 00:16:37,930
in our previous iteration, the B was
changed to a capital E. So we're about

364
00:16:37,930 --> 00:16:40,040
to encounter the problem, so this
is where we're going to

365
00:16:40,040 --> 00:16:41,130
dive into the debugging.

366
00:16:41,130 --> 00:16:43,365
But does anybody have any questions
about what we've done so far?

367
00:16:43,365 --> 00:16:46,770

368
00:16:46,770 --> 00:16:47,910
Fantastic.

369
00:16:47,910 --> 00:16:52,710
>> So we're about to execute this if
condition, plain text bracket I closed

370
00:16:52,710 --> 00:16:57,500
bracket greater than A and plain text I
less than or equal to Z. But before

371
00:16:57,500 --> 00:17:00,450
I go into that, because this is where
I know my error is, I want to point

372
00:17:00,450 --> 00:17:06,859
out plain text of I. So
let's put print out.

373
00:17:06,859 --> 00:17:12,020
It does equal the character A, so that
seems so far, all is well and good.

374
00:17:12,020 --> 00:17:14,740
>> So I expect this line per my logic,
this line should be true.

375
00:17:14,740 --> 00:17:16,099
It's a capital letter.

376
00:17:16,099 --> 00:17:20,599
But if I hit n, we do realize that this
line, in fact, did not execute.

377
00:17:20,599 --> 00:17:22,609
I jumped down to the else if.

378
00:17:22,609 --> 00:17:25,460
Why did that happen?

379
00:17:25,460 --> 00:17:27,480
>> STUDENT: Because you have your condition
of plain text is greater

380
00:17:27,480 --> 00:17:29,130
than A, not equal or greater than.

381
00:17:29,130 --> 00:17:32,260
>> JASON HIRSCHHORN: So I had my plain text
I is greater than A, not greater

382
00:17:32,260 --> 00:17:32,850
than or equal to.

383
00:17:32,850 --> 00:17:38,130
So clearly, the capital A did not
trigger this if condition, and we did

384
00:17:38,130 --> 00:17:40,520
not step into it, and we did
not do the necessary shift.

385
00:17:40,520 --> 00:17:41,360
So that's it, actually.

386
00:17:41,360 --> 00:17:42,920
I figured out my bug.

387
00:17:42,920 --> 00:17:46,775
I could go back in my source file,
change it, and update it and

388
00:17:46,775 --> 00:17:47,855
run Check 50 again.

389
00:17:47,855 --> 00:17:52,590
>> But we'll see, just for pedagogy's
sake, if I keep going.

390
00:17:52,590 --> 00:17:59,580
The else if doesn't execute either, but
what instead equals is the command

391
00:17:59,580 --> 00:18:00,500
that doesn't change.

392
00:18:00,500 --> 00:18:04,840
So it's not changed at all, and if I
print plain text here, we'll see going

393
00:18:04,840 --> 00:18:08,250
through that for loop didn't, in fact,
change that second character at all.

394
00:18:08,250 --> 00:18:09,600
It's still a capital A.

395
00:18:09,600 --> 00:18:12,690
>> So again, we debugged our error.

396
00:18:12,690 --> 00:18:17,380
We realized that there was
some logic missing.

397
00:18:17,380 --> 00:18:20,590
And we debugged it ahead of time before
actually executing that line,

398
00:18:20,590 --> 00:18:24,320
but you would have noticed had we just
hit Next and jump to that else if,

399
00:18:24,320 --> 00:18:26,710
that means that that if condition
was not true.

400
00:18:26,710 --> 00:18:29,550
We did not, in fact, get
the result we expected.

401
00:18:29,550 --> 00:18:33,240
So then we could have been prompted, had
we not been so astute, to look at

402
00:18:33,240 --> 00:18:38,510
that if condition and check if, in fact,
our condition should evaluate to

403
00:18:38,510 --> 00:18:41,150
true in the current context.

404
00:18:41,150 --> 00:18:42,880
>> That's all for debugging this program.

405
00:18:42,880 --> 00:18:45,340
Does anybody have any questions?

406
00:18:45,340 --> 00:18:50,486
What command could I hit to quit GDB?

407
00:18:50,486 --> 00:18:53,900
Q. And then I'll be prompted,
quit anyway?

408
00:18:53,900 --> 00:18:54,390
Yes or no.

409
00:18:54,390 --> 00:18:58,440
I'll hit yes, and I'll have quit GDB.

410
00:18:58,440 --> 00:19:00,860
>> So that was a quick primer to GDB.

411
00:19:00,860 --> 00:19:03,430
Actually, in a real scenario,
I did this at office hours.

412
00:19:03,430 --> 00:19:06,710
I GDBed this exact program at
office hours with a student.

413
00:19:06,710 --> 00:19:12,410
And if we go back to the commands we saw
before, we used break main, first

414
00:19:12,410 --> 00:19:13,190
thing we did.

415
00:19:13,190 --> 00:19:16,060
We used run with command line arguments,
second thing we did.

416
00:19:16,060 --> 00:19:18,520
We used next a lot to move
us through lines.

417
00:19:18,520 --> 00:19:20,310
And again, the short version
of next is n.

418
00:19:20,310 --> 00:19:22,920
That's in the parentheses
in gray on the slide.

419
00:19:22,920 --> 00:19:28,590
>> We did not use step, but we didn't
necessarily need to for this case.

420
00:19:28,590 --> 00:19:32,150
But we might use it in a bit later
on today if we are debugging, for

421
00:19:32,150 --> 00:19:36,500
example, binary search when binary
search is called in a separate

422
00:19:36,500 --> 00:19:38,200
function but there's
some error with it.

423
00:19:38,200 --> 00:19:40,440
We're going to want to step into
the call to binary search and

424
00:19:40,440 --> 00:19:41,840
actually debug it.

425
00:19:41,840 --> 00:19:45,130
List we didn't use either because we had
a good sense of our code, but if I

426
00:19:45,130 --> 00:19:48,420
did want to get a sense of what code I
was around, I could just use list.

427
00:19:48,420 --> 00:19:50,310
>> Print we used, info locals we used.

428
00:19:50,310 --> 00:19:53,260
Continue we didn't need to use in this
case, neither did we need to use

429
00:19:53,260 --> 00:19:55,060
disable, but we did use quit.

430
00:19:55,060 --> 00:19:57,850
Again, these 10 commands,
practice them.

431
00:19:57,850 --> 00:20:00,770
If you understand these 10 commands,
you should be set for debugging any

432
00:20:00,770 --> 00:20:02,525
issue with GDB.

433
00:20:02,525 --> 00:20:05,230

434
00:20:05,230 --> 00:20:08,420
>> So we're about to go on, again, to the
crux of section today, going over

435
00:20:08,420 --> 00:20:09,720
these sorting and searching
algorithms.

436
00:20:09,720 --> 00:20:14,075
Before we do so, again, any questions,
comments, concerns for GDB?

437
00:20:14,075 --> 00:20:16,750

438
00:20:16,750 --> 00:20:20,960
So is everybody going to use
GDB rather than printf?

439
00:20:20,960 --> 00:20:24,550
So everybody, for perpetuity's sake,
everybody is nodding their head right

440
00:20:24,550 --> 00:20:27,400
now, so I will see you at office hours
and all the TFs will see you and

441
00:20:27,400 --> 00:20:29,460
they'll say, show me how to use
GDB, and you'll be able

442
00:20:29,460 --> 00:20:31,240
to show them, right?

443
00:20:31,240 --> 00:20:31,760
Kind of?

444
00:20:31,760 --> 00:20:32,640
Maybe hopefully.

445
00:20:32,640 --> 00:20:33,670
Cool.

446
00:20:33,670 --> 00:20:35,790
>> So we're going to move into
sorting and searching.

447
00:20:35,790 --> 00:20:40,710
You'll see I have a list already sorted
for us, but that is not going

448
00:20:40,710 --> 00:20:42,220
to be the case always.

449
00:20:42,220 --> 00:20:49,170
So in the problem set specification for
problem set three, you have shorts

450
00:20:49,170 --> 00:20:51,410
that you can watch, and it actually
asks you to watch those shorts.

451
00:20:51,410 --> 00:20:55,090
Also in lecture last week, we went over
a lot of these algorithms, so I'm

452
00:20:55,090 --> 00:20:59,150
not going to spend time in class going
over these algorithms again or drawing

453
00:20:59,150 --> 00:21:01,130
pictures for how these
algorithms work.

454
00:21:01,130 --> 00:21:04,030
Again, that information you can re-watch
lecture, or that information

455
00:21:04,030 --> 00:21:08,570
is captured outstandingly on the shorts
for these searches, all of

456
00:21:08,570 --> 00:21:10,920
which are available at cs50.net.

457
00:21:10,920 --> 00:21:14,200
>> So instead, what we're going to
do is write these programs.

458
00:21:14,200 --> 00:21:18,190
We have a sense, a mental model, of how
they work, and so what we're going

459
00:21:18,190 --> 00:21:20,210
to do is code them for real.

460
00:21:20,210 --> 00:21:23,430
We're going to turn that mental model,
that picture, if you will, into the

461
00:21:23,430 --> 00:21:24,960
actual code.

462
00:21:24,960 --> 00:21:28,460
And if you were a little confused or
hazy on the mental model, I totally

463
00:21:28,460 --> 00:21:28,770
understand.

464
00:21:28,770 --> 00:21:30,540
>> We're not actually going to
jump to code straightaway.

465
00:21:30,540 --> 00:21:36,030
So while this prompt in this slide asks
you to code binary search, and

466
00:21:36,030 --> 00:21:39,470
actually, an iterative version of
binary search, the first thing I

467
00:21:39,470 --> 00:21:42,370
really want you to do is
write some pseudocode.

468
00:21:42,370 --> 00:21:47,020
So you have this mental model
of how binary search works.

469
00:21:47,020 --> 00:21:50,060
Take out a sheet of paper if you have
one readily available, or open up a

470
00:21:50,060 --> 00:21:52,520
text editor, and I'd like
everybody to write.

471
00:21:52,520 --> 00:21:57,470
Take four minutes to write the
pseudocode for binary search.

472
00:21:57,470 --> 00:21:58,990
>> Again, think about that mental model.

473
00:21:58,990 --> 00:22:01,980
I'll come around if you have questions
and we can draw the picture out.

474
00:22:01,980 --> 00:22:06,220
But first, before we start programming,
I'd like to write the

475
00:22:06,220 --> 00:22:09,920
pseudocode for binary search so when we
dive in, we have some direction as

476
00:22:09,920 --> 00:22:12,110
to where we should head.

477
00:22:12,110 --> 00:22:15,330
>> STUDENT: Can we assume the array of
values we get is already sorted?

478
00:22:15,330 --> 00:22:17,960
>> JASON HIRSCHHORN: So for binary search
to work-- excellent question-- you

479
00:22:17,960 --> 00:22:20,970
have to take in a sorted
array of values.

480
00:22:20,970 --> 00:22:22,290
So assume it will work.

481
00:22:22,290 --> 00:22:23,480
We'll go back to this slide.

482
00:22:23,480 --> 00:22:27,220
You'll see in purple the function
declaration is bool binary_search int

483
00:22:27,220 --> 00:22:29,230
value, int values, int n.

484
00:22:29,230 --> 00:22:32,910
This should look familiar if you've
already approached or gotten your

485
00:22:32,910 --> 00:22:34,580
hands dirty with the problem set.

486
00:22:34,580 --> 00:22:35,910
>> But that's your function declaration.

487
00:22:35,910 --> 00:22:39,080
Again, shouldn't need to worry about
that much at this moment.

488
00:22:39,080 --> 00:22:43,660
What I really want you to do is take
four minutes to pseudocode binary

489
00:22:43,660 --> 00:22:46,380
search, and then we'll go
over that as a group.

490
00:22:46,380 --> 00:22:47,500
And I will come around.

491
00:22:47,500 --> 00:22:49,590
If you have questions, feel
free to raise your hand.

492
00:22:49,590 --> 00:25:07,110

493
00:25:07,110 --> 00:25:09,680
>> Why don't you take two more minutes
to finish up the pseudocode?

494
00:25:09,680 --> 00:25:13,690

495
00:25:13,690 --> 00:25:15,820
I know this may seem ridiculous that
we're spending so much time on

496
00:25:15,820 --> 00:25:20,350
something that's not even actually in
C, but especially for these more

497
00:25:20,350 --> 00:25:24,030
challenging algorithms and problem
sets that we have to figure out,

498
00:25:24,030 --> 00:25:27,210
starting in pseudocode not worrying
about the syntax, just worrying about

499
00:25:27,210 --> 00:25:29,150
the logic, is incredibly helpful.

500
00:25:29,150 --> 00:25:32,720
And that way, you're not solving two
incredibly difficult problems at once.

501
00:25:32,720 --> 00:25:35,390
You're just focusing on the logic, and
then you move into the syntax.

502
00:25:35,390 --> 00:25:59,960

503
00:25:59,960 --> 00:26:01,385
>> OK.

504
00:26:01,385 --> 00:26:03,680
Let's start going through
the pseudocode.

505
00:26:03,680 --> 00:26:05,380
I have written up here, binary
search pseudocode.

506
00:26:05,380 --> 00:26:07,360
We'll write this on the
board together.

507
00:26:07,360 --> 00:26:10,040
Or I'll write it and you'll give
me the prompts I need.

508
00:26:10,040 --> 00:26:15,010
So can anybody give me the first
line of the pseudocode you

509
00:26:15,010 --> 00:26:18,350
wrote for binary search?

510
00:26:18,350 --> 00:26:20,258
Yes, Annie?

511
00:26:20,258 --> 00:26:22,698
>> STUDENT: While the length of the
list is greater than zero.

512
00:26:22,698 --> 00:26:26,114

513
00:26:26,114 --> 00:26:34,880
>> JASON HIRSCHHORN: While length
of list greater than zero.

514
00:26:34,880 --> 00:26:38,810
And again, we see some C-looking
syntactical things on here.

515
00:26:38,810 --> 00:26:41,550
But most of this is in English.

516
00:26:41,550 --> 00:26:43,980
Did anybody have any line they put
before this in their pseudo-code?

517
00:26:43,980 --> 00:26:47,280

518
00:26:47,280 --> 00:26:50,210
>> STUDENT: Get an array
of sorted numbers.

519
00:26:50,210 --> 00:26:53,600
>> JASON HIRSCHHORN: You wrote "get an
array of sorted numbers." Per the

520
00:26:53,600 --> 00:26:56,140
function declaration, we'll be passing
an array of sorted numbers.

521
00:26:56,140 --> 00:26:57,280
>> STUDENT: [INAUDIBLE].

522
00:26:57,280 --> 00:26:59,030
>> JASON HIRSCHHORN: So
we will have that.

523
00:26:59,030 --> 00:27:01,820
But yes, if we didn't have that, we
would need to sort our array of

524
00:27:01,820 --> 00:27:04,850
numbers, because binary search
only works on sorted arrays.

525
00:27:04,850 --> 00:27:11,300
So while length of list equals zero, I'm
going to put in some curly braces

526
00:27:11,300 --> 00:27:15,420
to make it look a little bit more like
C. But while, seems to map onto a

527
00:27:15,420 --> 00:27:19,550
while loop, so inside this while
loop what do we need to

528
00:27:19,550 --> 00:27:22,000
do for binary search?

529
00:27:22,000 --> 00:27:25,530
>> Someone else who has not given me an
answer yet but who wrote this?

530
00:27:25,530 --> 00:27:31,750

531
00:27:31,750 --> 00:27:33,320
>> STUDENT: Go to the middle of the list.

532
00:27:33,320 --> 00:27:33,980
>> JASON HIRSCHHORN: Tom.

533
00:27:33,980 --> 00:27:35,230
Go to the middle of the list.

534
00:27:35,230 --> 00:27:43,290

535
00:27:43,290 --> 00:27:45,530
And the follow-up question, what
do we do once we're at the

536
00:27:45,530 --> 00:27:46,870
middle of the list?

537
00:27:46,870 --> 00:27:49,310
>> STUDENT: Do a check whether that's
the number you're looking for.

538
00:27:49,310 --> 00:27:50,120
>> JASON HIRSCHHORN: Excellent.

539
00:27:50,120 --> 00:28:05,500
Go the middle of the list and check
if our value is there--

540
00:28:05,500 --> 00:28:06,515
fantastic.

541
00:28:06,515 --> 00:28:10,460
Did anybody have anything else
that was different than this?

542
00:28:10,460 --> 00:28:11,210
That's exactly right.

543
00:28:11,210 --> 00:28:13,800
>> The first thing we do in binary search
is go to the middle of the list and

544
00:28:13,800 --> 00:28:15,870
check to see if our value is there.

545
00:28:15,870 --> 00:28:19,682
So I assume if our value is
there, what do we do?

546
00:28:19,682 --> 00:28:21,610
>> STUDENT: We return zero [INAUDIBLE].

547
00:28:21,610 --> 00:28:23,400
>> JASON HIRSCHHORN: Yeah, if our
value is there, we found it.

548
00:28:23,400 --> 00:28:27,950
So we can tell some way, however this
function is defined, we tell the user

549
00:28:27,950 --> 00:28:28,520
we found it.

550
00:28:28,520 --> 00:28:30,950
If it's not there, though, that's
where this gets tricky.

551
00:28:30,950 --> 00:28:35,120
So if it's not there, somebody else who
was working on binary search or

552
00:28:35,120 --> 00:28:36,830
has an idea now, what do we do?

553
00:28:36,830 --> 00:28:37,830
>> STUDENT: Question.

554
00:28:37,830 --> 00:28:38,100
>> JASON HIRSCHHORN: Yes?

555
00:28:38,100 --> 00:28:39,920
>> STUDENT: Is the array already sorted?

556
00:28:39,920 --> 00:28:42,200
>> JASON HIRSCHHORN: Yes, we're assuming
the array is already sorted.

557
00:28:42,200 --> 00:28:46,480
>> STUDENT: So then you have to check if
the value that you see is greater than

558
00:28:46,480 --> 00:28:51,745
the value that you want, you can move
to the middle of the other half.

559
00:28:51,745 --> 00:28:54,110
>> JASON HIRSCHHORN: So if the middle of
the list is greater than what we're

560
00:28:54,110 --> 00:28:57,440
looking for, then we do what?

561
00:28:57,440 --> 00:28:58,320
We move where?

562
00:28:58,320 --> 00:29:01,400
>> STUDENT: You want to move to
the half of the list with

563
00:29:01,400 --> 00:29:02,780
numbers lower than that.

564
00:29:02,780 --> 00:29:04,460
>> JASON HIRSCHHORN: So we'll
call that the left.

565
00:29:04,460 --> 00:29:15,435
So if middle is greater, we can search
the left half of the list.

566
00:29:15,435 --> 00:29:20,620

567
00:29:20,620 --> 00:29:22,980
And then by search, what
do I mean by search?

568
00:29:22,980 --> 00:29:24,010
>> STUDENT: [INAUDIBLE].

569
00:29:24,010 --> 00:29:24,410
>> JASON HIRSCHHORN: We go to the middle.

570
00:29:24,410 --> 00:29:25,740
We actually repeat this thing.

571
00:29:25,740 --> 00:29:29,210
We go back through our while loop.

572
00:29:29,210 --> 00:29:31,480
I'll give you the last one--

573
00:29:31,480 --> 00:29:39,047
else, if, middle is less than what
we do, what do we do here?

574
00:29:39,047 --> 00:29:40,360
>> STUDENT: Go to the right.

575
00:29:40,360 --> 00:29:41,610
>> JASON HIRSCHHORN: Search the right.

576
00:29:41,610 --> 00:29:47,440

577
00:29:47,440 --> 00:29:51,710
This looks good, but does anybody have
anything that we may be missing or

578
00:29:51,710 --> 00:29:53,200
anything else that you put
in your pseudo-code?

579
00:29:53,200 --> 00:29:57,080

580
00:29:57,080 --> 00:29:58,410
So this is what we have so far.

581
00:29:58,410 --> 00:30:00,960
While the length of the list is greater
than zero, we're going to go

582
00:30:00,960 --> 00:30:03,220
to the middle of the list and
check if our value is there.

583
00:30:03,220 --> 00:30:06,970
>> If the middle is greater, we're going to
search left, else if the middle is

584
00:30:06,970 --> 00:30:09,230
less, we're going to search the right.

585
00:30:09,230 --> 00:30:14,430
So we've all had some familiarity with
the terms we use in computer science

586
00:30:14,430 --> 00:30:15,550
and the tools we have.

587
00:30:15,550 --> 00:30:18,300
But you'll already notice we were
speaking in English, but we found a

588
00:30:18,300 --> 00:30:24,790
lot of things that seemed to map on to
tools we have in our coding tool kit.

589
00:30:24,790 --> 00:30:27,210
So right off the bat, we're not
going to actually code yet.

590
00:30:27,210 --> 00:30:33,300
>> What do we see here in English that maps
on to things we can write in C?

591
00:30:33,300 --> 00:30:34,560
>> STUDENT: While.

592
00:30:34,560 --> 00:30:35,320
>> JASON HIRSCHHORN: While.

593
00:30:35,320 --> 00:30:40,610
So this while right here
maps on to what?

594
00:30:40,610 --> 00:30:42,630
>> STUDENT: A while loop.

595
00:30:42,630 --> 00:30:43,200
>> JASON HIRSCHHORN: A while loop?

596
00:30:43,200 --> 00:30:44,540
Or probably, more generally, a loop.

597
00:30:44,540 --> 00:30:46,260
We want to do something over and over.

598
00:30:46,260 --> 00:30:49,050
So we're going to code a loop.

599
00:30:49,050 --> 00:30:51,640
And we already know, because we've done
this a couple of times and we

600
00:30:51,640 --> 00:30:54,180
have plenty of examples out there,
how actually to write

601
00:30:54,180 --> 00:30:55,310
this index for a loop.

602
00:30:55,310 --> 00:30:56,160
So that should be pretty easy.

603
00:30:56,160 --> 00:30:58,070
We should be able to get that
started pretty quickly.

604
00:30:58,070 --> 00:31:01,830
>> What else do we see in here?

605
00:31:01,830 --> 00:31:06,820
What other structures syntaxes, things
that we're familiar with in C, do we

606
00:31:06,820 --> 00:31:09,790
already have a sense of based
off of the words we used?

607
00:31:09,790 --> 00:31:10,830
Yes, Anna?

608
00:31:10,830 --> 00:31:11,360
[INAUDIBLE]

609
00:31:11,360 --> 00:31:12,990
just kidding.

610
00:31:12,990 --> 00:31:13,540
Anna, go ahead.

611
00:31:13,540 --> 00:31:14,530
>> STUDENT: If and else.

612
00:31:14,530 --> 00:31:16,260
>> JASON HIRSCHHORN: If and
else-- right here.

613
00:31:16,260 --> 00:31:18,840
So what do those look like?

614
00:31:18,840 --> 00:31:20,420
>> STUDENT: An if else statement.

615
00:31:20,420 --> 00:31:21,560
>> JASON HIRSCHHORN: Yeah,
conditions, right?

616
00:31:21,560 --> 00:31:24,650
So we'll probably need to
write some conditions.

617
00:31:24,650 --> 00:31:31,185
And again, though maybe confusing at
first, we generally have a sense now

618
00:31:31,185 --> 00:31:34,010
of how to write conditions and
the syntax for conditions.

619
00:31:34,010 --> 00:31:36,850
And if we don't, we just look up the
syntax for conditions, cut and paste

620
00:31:36,850 --> 00:31:39,950
that, because we know we
need a condition here.

621
00:31:39,950 --> 00:31:44,910
Any other things we see that map onto
things we might need to do in C?

622
00:31:44,910 --> 00:31:48,312

623
00:31:48,312 --> 00:31:48,960
Yeah, Aleha?

624
00:31:48,960 --> 00:31:50,370
>> STUDENT: This might be obvious,
by just checking if a

625
00:31:50,370 --> 00:31:51,990
value equals something.

626
00:31:51,990 --> 00:31:54,578
>> JASON HIRSCHHORN: So how do we check
and-- so go to the middle of the list

627
00:31:54,578 --> 00:31:55,610
and check if our value is there?

628
00:31:55,610 --> 00:31:56,570
How do we do that in C?

629
00:31:56,570 --> 00:31:58,450
What's the syntax for that?

630
00:31:58,450 --> 00:31:59,235
>> STUDENT: Equals, equals.

631
00:31:59,235 --> 00:32:00,650
>> JASON HIRSCHHORN: Equals, equals.

632
00:32:00,650 --> 00:32:03,540
So this check is probably going
to be an equals, equals.

633
00:32:03,540 --> 00:32:04,510
So we'll know we need that somewhere.

634
00:32:04,510 --> 00:32:07,510
And actually, just in writing it,
we see those other things.

635
00:32:07,510 --> 00:32:11,400
We're going to have to do some
comparison operators in there--

636
00:32:11,400 --> 00:32:12,010
fantastic.

637
00:32:12,010 --> 00:32:14,980
So it actually looks like, by and
large, we haven't written a

638
00:32:14,980 --> 00:32:16,390
word of C code yet.

639
00:32:16,390 --> 00:32:20,610
But we got the mental model down
via lectures and those shorts.

640
00:32:20,610 --> 00:32:22,350
>> We wrote pseudo-code as a group.

641
00:32:22,350 --> 00:32:27,110
And already, we have 80% if not
90% of what we need to do.

642
00:32:27,110 --> 00:32:28,550
Now, we just need to code
it, which again, is a

643
00:32:28,550 --> 00:32:30,110
non-trivial problem to solve.

644
00:32:30,110 --> 00:32:31,890
But at least we're stuck on the logic.

645
00:32:31,890 --> 00:32:38,040
At least now when we go to office hours,
I can say, I know what I need

646
00:32:38,040 --> 00:32:40,160
to do, but can you remind
me of the syntax?

647
00:32:40,160 --> 00:32:42,940
Or even if office hours are crowded, you
can Google for the syntax, rather

648
00:32:42,940 --> 00:32:45,040
than being stuck on the logic.

649
00:32:45,040 --> 00:32:48,570
>> And again, rather than trying to solve
the logic and the syntax problems all

650
00:32:48,570 --> 00:32:51,900
at once, it is often much better to
break those two hard problems off into

651
00:32:51,900 --> 00:32:58,280
two more manageable ones and do the
pseudo-code first and then code in C.

652
00:32:58,280 --> 00:33:00,620
So let's see what I did for the
pseudo-code ahead of time.

653
00:33:00,620 --> 00:33:04,060
>> While the length of the list is greater
than zero, look at the middle

654
00:33:04,060 --> 00:33:05,090
of the list.

655
00:33:05,090 --> 00:33:09,610
If number found returned true, else
if number higher, search left.

656
00:33:09,610 --> 00:33:13,200
Else if number lower, search
right, return false.

657
00:33:13,200 --> 00:33:18,710
So that looks almost identical if not
nearly identical to what we wrote.

658
00:33:18,710 --> 00:33:23,030
Actually, Tom, what you said first,
breaking the middle of the list and if

659
00:33:23,030 --> 00:33:24,880
number found into two statements
is actually what I did.

660
00:33:24,880 --> 00:33:25,507
>> I combined them there.

661
00:33:25,507 --> 00:33:27,100
I should have listened to
you the first time.

662
00:33:27,100 --> 00:33:30,640
So that is the pseudo-code we have.

663
00:33:30,640 --> 00:33:35,060
If you want to now, sorry, go
back to our initial problem.

664
00:33:35,060 --> 00:33:37,780
Let's code binary.c.

665
00:33:37,780 --> 00:33:40,870
So implement an iterative version of
binary search using the following

666
00:33:40,870 --> 00:33:42,420
function declaration.

667
00:33:42,420 --> 00:33:44,550
>> And you don't need to copy
it down just yet.

668
00:33:44,550 --> 00:33:49,470
I'm actually going to open
up right here binary.c.

669
00:33:49,470 --> 00:33:52,880
So there is the function declaration
in the middle of the screen.

670
00:33:52,880 --> 00:33:57,570
And you'll see I took the pseudo-code
from on my sides, but almost identical

671
00:33:57,570 --> 00:33:59,740
to what we wrote, and
put that in for you.

672
00:33:59,740 --> 00:34:06,010
So now, let's take five minutes
to code this function.

673
00:34:06,010 --> 00:34:08,199
>> And again, if you have any questions,
raise your hand, let me know, I'll

674
00:34:08,199 --> 00:34:08,710
come around.

675
00:34:08,710 --> 00:34:09,800
>> STUDENT: [INAUDIBLE].

676
00:34:09,800 --> 00:34:12,380
>> JASON HIRSCHHORN: So I took the binary
search definition at the

677
00:34:12,380 --> 00:34:14,429
top, on line 12.

678
00:34:14,429 --> 00:34:16,429
That's what I got for my slide.

679
00:34:16,429 --> 00:34:20,940
And then all this pseudo-code I just
copy and pasted from the slide,

680
00:34:20,940 --> 00:34:22,190
pseudo-code slide.

681
00:34:22,190 --> 00:35:22,830

682
00:35:22,830 --> 00:35:26,786
I'm still not hearing [INAUDIBLE].

683
00:35:26,786 --> 00:37:13,010

684
00:37:13,010 --> 00:37:15,820
>> So if you have finished your
implementation, I want to check it.

685
00:37:15,820 --> 00:37:19,410
I emailed you the helpers.h file
earlier in this class.

686
00:37:19,410 --> 00:37:22,360
And it will be available online as well
for download for people watching

687
00:37:22,360 --> 00:37:24,750
this section time delayed.

688
00:37:24,750 --> 00:37:29,350
And I just used the generic distribution
code from pset3.

689
00:37:29,350 --> 00:37:34,590
So I took find.C, use my helpers.h file
rather than the helpers.h file

690
00:37:34,590 --> 00:37:36,280
that's given in the distribution code.

691
00:37:36,280 --> 00:37:39,310
>> And I had to make one other change in
find.C rather than calling just simply

692
00:37:39,310 --> 00:37:42,770
search, call binary_search.

693
00:37:42,770 --> 00:37:49,080
So if you want to test your code,
know that that is how to do it.

694
00:37:49,080 --> 00:37:52,530
In fact, when we'll be running this code
right now, I just made a copy of

695
00:37:52,530 --> 00:37:59,820
my pset3 directory, again, swapped out
the helpers files and then made that

696
00:37:59,820 --> 00:38:04,695
change in find.C to call binary_search
rather than simply search.

697
00:38:04,695 --> 00:40:08,620

698
00:40:08,620 --> 00:40:09,120
>> JASON HIRSCHHORN: Yes.

699
00:40:09,120 --> 00:40:11,258
You have a question?

700
00:40:11,258 --> 00:40:12,150
>> STUDENT: Nevermind.

701
00:40:12,150 --> 00:40:12,600
>> JASON HIRSCHHORN: No worries.

702
00:40:12,600 --> 00:40:13,370
Well, let's get started.

703
00:40:13,370 --> 00:40:15,090
We will code this as a group.

704
00:40:15,090 --> 00:40:16,050
One other note.

705
00:40:16,050 --> 00:40:20,600
Again, this is, can easily be swapped
in for Problem Set Three.

706
00:40:20,600 --> 00:40:25,530
I have my helpers.h file which, rather
than the helpers.h we're given,

707
00:40:25,530 --> 00:40:28,560
declares binary search, bubble
sort, and selection sort.

708
00:40:28,560 --> 00:40:37,400
And in find.c you'll notice on line,
what is that, line 68, we call binary

709
00:40:37,400 --> 00:40:39,160
search rather than search.

710
00:40:39,160 --> 00:40:42,930
So again, the code that is available
online or the code that you are

711
00:40:42,930 --> 00:40:46,590
creating right now can be easily swapped
in for p set 3 to check it.

712
00:40:46,590 --> 00:40:50,620
>> But first, let's code binary search.

713
00:40:50,620 --> 00:40:53,690
Our function declaration,
we return a bool.

714
00:40:53,690 --> 00:40:55,810
We take an integer called value.

715
00:40:55,810 --> 00:40:59,285
We take an array of integers called
values, and we take n be

716
00:40:59,285 --> 00:41:00,850
the size of the array.

717
00:41:00,850 --> 00:41:05,640
On line 10, right here, I have
sharp include stdbool.h.

718
00:41:05,640 --> 00:41:07,360
Does anybody know why that's there?

719
00:41:07,360 --> 00:41:12,180

720
00:41:12,180 --> 00:41:16,600
So what does that line of code do?

721
00:41:16,600 --> 00:41:19,880
>> STUDENT: It allows you to
use a bool return type.

722
00:41:19,880 --> 00:41:20,350
>> JASON HIRSCHHORN: Exactly.

723
00:41:20,350 --> 00:41:22,300
>> STUDENT: Or it's a library that allows
to use a bool return type.

724
00:41:22,300 --> 00:41:27,590
>> JASON HIRSCHHORN: So the sharp include
stdbool.h line gives me some

725
00:41:27,590 --> 00:41:31,340
definitions and declarations for things
that I am allowed to use in

726
00:41:31,340 --> 00:41:32,400
this library.

727
00:41:32,400 --> 00:41:36,570
So among those is saying that there's
this type called bool, and it can be

728
00:41:36,570 --> 00:41:37,750
true or false.

729
00:41:37,750 --> 00:41:39,010
So that's what that line does.

730
00:41:39,010 --> 00:41:41,680
And if I didn't have that line, I would
get in trouble for writing this

731
00:41:41,680 --> 00:41:43,520
word right here, bool, right there.

732
00:41:43,520 --> 00:41:44,140
Exactly right.

733
00:41:44,140 --> 00:41:46,430
So I need that in this code.

734
00:41:46,430 --> 00:41:47,690
OK.

735
00:41:47,690 --> 00:41:51,860
So this, again, is an iterative
version, not a recursive one.

736
00:41:51,860 --> 00:41:53,820
So let us get started.

737
00:41:53,820 --> 00:41:56,200
>> Let's start with this first
line of pseudo code.

738
00:41:56,200 --> 00:41:58,770
And hopefully, we will--
or not hopefully.

739
00:41:58,770 --> 00:42:00,530
We're going to go around the room.

740
00:42:00,530 --> 00:42:05,110
We'll go line by line, and I will help
you figure out the line that we need

741
00:42:05,110 --> 00:42:06,310
to write first.

742
00:42:06,310 --> 00:42:10,550
So while length of list
is greater than zero.

743
00:42:10,550 --> 00:42:12,680
Let's start in the front.

744
00:42:12,680 --> 00:42:15,190
What line should I write
here, in code?

745
00:42:15,190 --> 00:42:19,470
>> STUDENT: While parenthesis
n is greater than 0.

746
00:42:19,470 --> 00:42:21,900
>> JASON HIRSCHHORN: While
n is great than 0.

747
00:42:21,900 --> 00:42:26,550
So n is the size of a list,
and we're checking if--

748
00:42:26,550 --> 00:42:26,800
>> [INTERPOSING VOICES]

749
00:42:26,800 --> 00:42:27,660
>> JASON HIRSCHHORN: --sorry?

750
00:42:27,660 --> 00:42:29,360
>> STUDENT: How do we know that
n is the size of the list?

751
00:42:29,360 --> 00:42:29,690
>> JASON HIRSCHHORN: Sorry.

752
00:42:29,690 --> 00:42:34,690
Per the pset specification, the search
and sort functions you need to write,

753
00:42:34,690 --> 00:42:36,230
n is the size of the list.

754
00:42:36,230 --> 00:42:37,710
I forgot to explain that here.

755
00:42:37,710 --> 00:42:41,310
But yes. n is the size of
the list, in this case.

756
00:42:41,310 --> 00:42:44,740
So while n is greater than 0.

757
00:42:44,740 --> 00:42:45,580
OK.

758
00:42:45,580 --> 00:42:50,090
That may prove a bit problematic
though, if things go on.

759
00:42:50,090 --> 00:42:54,510
Because we will continue to know the
size of the list throughout this

760
00:42:54,510 --> 00:43:06,640
function, but say we start off
with an array of 5 integers.

761
00:43:06,640 --> 00:43:08,950
And we go through and we've
now narrowed it down to

762
00:43:08,950 --> 00:43:10,310
an array of 2 integers.

763
00:43:10,310 --> 00:43:12,160
Which 2 integers is that?

764
00:43:12,160 --> 00:43:15,895
The size is 2 now that we want to
look at, but which 2 is that?

765
00:43:15,895 --> 00:43:17,720
Does that make sense, that question?

766
00:43:17,720 --> 00:43:18,020
>> OK.

767
00:43:18,020 --> 00:43:19,120
I'll ask it again.

768
00:43:19,120 --> 00:43:26,640
So we start off with this array of 5
integers, and n equals 5, right?

769
00:43:26,640 --> 00:43:28,050
We'll run through here.

770
00:43:28,050 --> 00:43:31,560
we'll probably change the size,
right, as things go on.

771
00:43:31,560 --> 00:43:32,700
Which is what we say we want to do.

772
00:43:32,700 --> 00:43:34,150
We don't want to search
the full thing again.

773
00:43:34,150 --> 00:43:35,480
So say we change it to 2.

774
00:43:35,480 --> 00:43:36,970
We take half the list that's odd.

775
00:43:36,970 --> 00:43:38,800
So just pick 2.

776
00:43:38,800 --> 00:43:40,590
So now n equals 2.

777
00:43:40,590 --> 00:43:42,780
I apologize for the poor
dry erase markers.

778
00:43:42,780 --> 00:43:43,080
Right?

779
00:43:43,080 --> 00:43:45,670
And we're searching through the list
again with a list of size 2.

780
00:43:45,670 --> 00:43:48,580
Well, our array is still of size 5.

781
00:43:48,580 --> 00:43:51,920
We say we only want to
search 2 spots in it.

782
00:43:51,920 --> 00:43:53,590
So which 2 spots are those?

783
00:43:53,590 --> 00:43:57,640

784
00:43:57,640 --> 00:43:58,815
>> Does that make sense?

785
00:43:58,815 --> 00:44:00,290
Are they the left 2 spots?

786
00:44:00,290 --> 00:44:01,940
Are they the right 2 spots?

787
00:44:01,940 --> 00:44:03,540
Are they the middle 2 spots?

788
00:44:03,540 --> 00:44:06,350
We have broken the problem down, but we
actually don't know which part of

789
00:44:06,350 --> 00:44:11,600
the problem we're still looking at,
just by having these 2 variables.

790
00:44:11,600 --> 00:44:16,450
So we need a little bit more then,
while n is greater than 0.

791
00:44:16,450 --> 00:44:21,410
We need to know where that
n is in our actual array.

792
00:44:21,410 --> 00:44:26,660
>> So does anybody have a
change to this line?

793
00:44:26,660 --> 00:44:27,970
Most of this line is
perfectly correct.

794
00:44:27,970 --> 00:44:29,170
Is there another addition?

795
00:44:29,170 --> 00:44:32,510
Can we swap something out for n to
make this line a bit better?

796
00:44:32,510 --> 00:44:32,865
Mm-hm?

797
00:44:32,865 --> 00:44:38,040
>> STUDENT: Can you initialize a variable
like length to n that'll then be used

798
00:44:38,040 --> 00:44:39,600
later in the function?

799
00:44:39,600 --> 00:44:42,060
>> JASON HIRSCHHORN: So initialize
a variable length to n,

800
00:44:42,060 --> 00:44:42,900
and we use that later?

801
00:44:42,900 --> 00:44:47,070
But then we just update length and we
still run into this problem where we

802
00:44:47,070 --> 00:44:51,180
cut down the length of our problem,
but we never know where, actually,

803
00:44:51,180 --> 00:44:52,510
that length maps onto.

804
00:44:52,510 --> 00:44:54,790
>> STUDENT: Isn't that going to happen
later when you're saying, search left,

805
00:44:54,790 --> 00:44:55,746
search right?

806
00:44:55,746 --> 00:44:57,640
You're going to go to a different
area of your--

807
00:44:57,640 --> 00:44:59,110
>> JASON HIRSCHHORN: We're going to go
to an area, but how do we know

808
00:44:59,110 --> 00:45:01,150
which are to go to?

809
00:45:01,150 --> 00:45:03,800
If we only have the array and this
n, how do we know where to

810
00:45:03,800 --> 00:45:05,050
go to in the array.

811
00:45:05,050 --> 00:45:05,900
In the back, yes?

812
00:45:05,900 --> 00:45:07,507
>> STUDENT: Do you have, like, a lower
bound and an upper bound variable or

813
00:45:07,507 --> 00:45:08,586
something like that?

814
00:45:08,586 --> 00:45:09,060
>> JASON HIRSCHHORN: OK.

815
00:45:09,060 --> 00:45:10,780
So this is another idea.

816
00:45:10,780 --> 00:45:13,490
Rather than just keeping track of the
size, we keep track of the lower and

817
00:45:13,490 --> 00:45:14,770
upper bound variable.

818
00:45:14,770 --> 00:45:17,840
So how do we calculate the size from
a lower bound and upper bound?

819
00:45:17,840 --> 00:45:18,520
>> [INTERPOSING VOICES]

820
00:45:18,520 --> 00:45:19,710
>> JASON HIRSCHHORN: Subtraction.

821
00:45:19,710 --> 00:45:23,650
And also keeping track of the lower
bound and upper bound to let us know,

822
00:45:23,650 --> 00:45:26,215
are we searching these two?

823
00:45:26,215 --> 00:45:28,220
Are we searching these two over here?

824
00:45:28,220 --> 00:45:29,540
Are we searching the middle two?

825
00:45:29,540 --> 00:45:32,810
Probably not the middle two, because
this, in fact, is binary search.

826
00:45:32,810 --> 00:45:37,320
But now we'll be able to get the size,
but also the limits of the array.

827
00:45:37,320 --> 00:45:40,020
In essence, if we have our giant
phone book, we rip it in half.

828
00:45:40,020 --> 00:45:42,990
We now know where that smaller
phone book is.

829
00:45:42,990 --> 00:45:45,260
But we're not actually ripping
the phone book in half.

830
00:45:45,260 --> 00:45:48,570
We still need to know where the
new bounds of our problem is.

831
00:45:48,570 --> 00:45:51,645
Does anybody have any questions
about that?

832
00:45:51,645 --> 00:45:52,440
Yes?

833
00:45:52,440 --> 00:45:56,020
>> STUDENT: Would it work by creating a
variable, i, that you then just shift

834
00:45:56,020 --> 00:46:00,770
the position of i relative to its
current position, and the length, n?

835
00:46:00,770 --> 00:46:01,710
>> JASON HIRSCHHORN: And what is i?

836
00:46:01,710 --> 00:46:04,110
>> STUDENT: Like i being like sort of--

837
00:46:04,110 --> 00:46:08,040
Like you would initialize i to be the
middle position of the array.

838
00:46:08,040 --> 00:46:12,540
And then, if the value at position i in
the middle of the array in found to

839
00:46:12,540 --> 00:46:17,870
be less than the value you need, i now
becomes the length of the array, plus

840
00:46:17,870 --> 00:46:19,215
the value of i divided by 2.

841
00:46:19,215 --> 00:46:20,270
Like, see, you shift i--

842
00:46:20,270 --> 00:46:20,770
>> JASON HIRSCHHORN: Right.

843
00:46:20,770 --> 00:46:21,165
>> STUDENT: --up to the--

844
00:46:21,165 --> 00:46:24,010
>> JASON HIRSCHHORN: So I am almost
positive that will work.

845
00:46:24,010 --> 00:46:26,800
But the point being, you need two
pieces of information here.

846
00:46:26,800 --> 00:46:30,050
You can do it with beginning and end,
or you can do it with size, and then

847
00:46:30,050 --> 00:46:31,060
some marker.

848
00:46:31,060 --> 00:46:32,630
But you do need two pieces
of information here.

849
00:46:32,630 --> 00:46:34,160
You can't get by with just one.

850
00:46:34,160 --> 00:46:35,830
Does that makes sense?

851
00:46:35,830 --> 00:46:39,560
>> So we're going to go through, and
we're going to do [INAUDIBLE]

852
00:46:39,560 --> 00:46:41,330
and create some markers.

853
00:46:41,330 --> 00:46:42,690
So what'd you write in your code?

854
00:46:42,690 --> 00:46:46,190
>> STUDENT: I just said int bound
one is equal to 0.

855
00:46:46,190 --> 00:46:47,790
>> JASON HIRSCHHORN: Let's call
that int, beginning.

856
00:46:47,790 --> 00:46:49,140
>> STUDENT: OK.

857
00:46:49,140 --> 00:46:50,590
>> JASON HIRSCHHORN: That makes
more sense for me.

858
00:46:50,590 --> 00:46:51,670
And?

859
00:46:51,670 --> 00:46:54,340
>> STUDENT: I said, I guess, int ending.

860
00:46:54,340 --> 00:46:55,870
>> JASON HIRSCHHORN: int ending.

861
00:46:55,870 --> 00:46:57,640
>> STUDENT: I guess, n minus 1,
or something like that.

862
00:46:57,640 --> 00:46:59,100
Like, the last element.

863
00:46:59,100 --> 00:47:02,310
>> JASON HIRSCHHORN: So you wrote, int
beginning equals 0, semicolon, and int

864
00:47:02,310 --> 00:47:04,320
ending equals n minus 1, semicolon.

865
00:47:04,320 --> 00:47:06,850
So essentially, what we're doing
here, 0 the first position.

866
00:47:06,850 --> 00:47:09,570
And as we know in arrays, they don't go
up to n, they go up to n minus 1.

867
00:47:09,570 --> 00:47:11,110
So we have some bounds of our array.

868
00:47:11,110 --> 00:47:15,730
And these initial bounds happen to be
the initial bounds of our problem.

869
00:47:15,730 --> 00:47:16,640
OK.

870
00:47:16,640 --> 00:47:19,200
So that sounds good.

871
00:47:19,200 --> 00:47:22,380
Then if we go back to this line, while
length of list is greater than 0,

872
00:47:22,380 --> 00:47:24,752
what, instead of n, should
we put in here?

873
00:47:24,752 --> 00:47:28,820
>> STUDENT: Write ending minus beginning.

874
00:47:28,820 --> 00:47:34,780
>> JASON HIRSCHHORN: While ending minus
beginning is greater than 0?

875
00:47:34,780 --> 00:47:35,480
OK.

876
00:47:35,480 --> 00:47:37,730
And we could, if we wanted to
make that a bit nicer, what

877
00:47:37,730 --> 00:47:38,980
else could we do?

878
00:47:38,980 --> 00:47:41,650

879
00:47:41,650 --> 00:47:43,412
If we wanted to clean
this code up a bit?

880
00:47:43,412 --> 00:47:46,716

881
00:47:46,716 --> 00:47:48,180
How can we get rid of the 0?

882
00:47:48,180 --> 00:47:51,560

883
00:47:51,560 --> 00:47:52,690
This is just a style question.

884
00:47:52,690 --> 00:47:53,690
It's correct right now.

885
00:47:53,690 --> 00:47:54,870
>> STUDENT: Ending doesn't
equal beginning?

886
00:47:54,870 --> 00:47:55,740
>> JASON HIRSCHHORN: We can do what?

887
00:47:55,740 --> 00:47:56,730
>> [INTERPOSING VOICES]

888
00:47:56,730 --> 00:47:57,330
>> STUDENT: Ending is greater?

889
00:47:57,330 --> 00:47:57,720
>> JASON HIRSCHHORN: Yeah.

890
00:47:57,720 --> 00:48:01,110
We can just do while ending
is greater than beginning.

891
00:48:01,110 --> 00:48:03,580
Right.

892
00:48:03,580 --> 00:48:06,240
We added beginning to the other side
of that, and we got rid of the 0.

893
00:48:06,240 --> 00:48:08,000
So this just looks a
little bit cleaner.

894
00:48:08,000 --> 00:48:08,990
OK.

895
00:48:08,990 --> 00:48:11,460
So, while length of list is 0, we wrote
that, while ending is greater

896
00:48:11,460 --> 00:48:12,240
than beginning.

897
00:48:12,240 --> 00:48:19,840
We're going to put in our necessary
curly braces, and then the first thing

898
00:48:19,840 --> 00:48:22,090
we want to do is look at
them in a little list.

899
00:48:22,090 --> 00:48:22,510
You?

900
00:48:22,510 --> 00:48:23,320
Can you give me the--

901
00:48:23,320 --> 00:48:26,460
>> STUDENT: If parenthesis
value square bracket--

902
00:48:26,460 --> 00:48:30,450
>> JASON HIRSCHHORN: If parentheses
value square bracket.

903
00:48:30,450 --> 00:48:33,210
>> STUDENT: Ending divided by 2.

904
00:48:33,210 --> 00:48:33,952
>> JASON HIRSCHHORN: Ending?

905
00:48:33,952 --> 00:48:35,280
>> STUDENT: I see a problem with your--

906
00:48:35,280 --> 00:48:35,750
>> JASON HIRSCHHORN: OK.

907
00:48:35,750 --> 00:48:39,150
Well, look at the middle.

908
00:48:39,150 --> 00:48:41,226
How do we know what the middle is?

909
00:48:41,226 --> 00:48:42,450
Yeah.

910
00:48:42,450 --> 00:48:43,070
So let me delete that code.

911
00:48:43,070 --> 00:48:46,360
How do we know what the middle is?

912
00:48:46,360 --> 00:48:48,003
In anything, when you have the beginning
and the end, how do you find

913
00:48:48,003 --> 00:48:48,876
the middle?

914
00:48:48,876 --> 00:48:49,590
>> STUDENT: You average.

915
00:48:49,590 --> 00:48:51,820
>> STUDENT: You add them
together and then--

916
00:48:51,820 --> 00:48:53,150
>> JASON HIRSCHHORN: Add them
together and then?

917
00:48:53,150 --> 00:48:54,090
>> STUDENT: And you average.

918
00:48:54,090 --> 00:48:55,050
Divide it by 2.

919
00:48:55,050 --> 00:48:56,500
>> JASON HIRSCHHORN: Add them
together and divide by 2.

920
00:48:56,500 --> 00:48:59,400
So int middle equals?

921
00:48:59,400 --> 00:49:01,120
Tom, you can give it to me?

922
00:49:01,120 --> 00:49:03,550
>> STUDENT: Beginning plus ending--

923
00:49:03,550 --> 00:49:04,950
>> JASON HIRSCHHORN: Beginning
plus ending.

924
00:49:04,950 --> 00:49:06,880
>> STUDENT: All, bracket, divided by 2.

925
00:49:06,880 --> 00:49:10,940
>> JASON HIRSCHHORN: All, in parentheses,
divided by 2.

926
00:49:10,940 --> 00:49:16,300
So that gives me the middle
of anything, correct?

927
00:49:16,300 --> 00:49:18,980
>> STUDENT: You also need to round it up.

928
00:49:18,980 --> 00:49:19,990
>> JASON HIRSCHHORN: What do you
mean, I need to round it up?

929
00:49:19,990 --> 00:49:20,400
>> [INTERPOSING VOICES]

930
00:49:20,400 --> 00:49:24,520
>> STUDENT: Because if It's an odd
number, then it's like--

931
00:49:24,520 --> 00:49:25,440
>> JASON HIRSCHHORN: Well, OK.

932
00:49:25,440 --> 00:49:26,360
So I could round it up.

933
00:49:26,360 --> 00:49:33,350
But if it's an odd number, a 5, I can
taking 1 away from the middle.

934
00:49:33,350 --> 00:49:35,665
Or if it's an even number, rather,
that's a better case.

935
00:49:35,665 --> 00:49:39,600
If it's 4, we only have 4, I can take
the first "middle", quote, unquote or

936
00:49:39,600 --> 00:49:41,760
the second "middle" one.

937
00:49:41,760 --> 00:49:46,390
Either would work for a binary search,
so I don't actually need to round it.

938
00:49:46,390 --> 00:49:48,640
But there is one other thing I
need to look at this line.

939
00:49:48,640 --> 00:49:50,530
We might not realize it yet,
but we'll come back to it.

940
00:49:50,530 --> 00:49:53,200
Because this line actually still
needs one other thing.

941
00:49:53,200 --> 00:49:55,990
>> But so far, we've written
four lines of code.

942
00:49:55,990 --> 00:49:58,120
We've got our beginning
and ending markers.

943
00:49:58,120 --> 00:50:01,320
We have our while loop, which maps
on directly to our pseudocode.

944
00:50:01,320 --> 00:50:05,790
We're looking at the middle that maps
directly onto our pseudocode.

945
00:50:05,790 --> 00:50:09,070
I would say this goes to the middle
of the list, this line of code.

946
00:50:09,070 --> 00:50:11,560
And then, once we go to the middle of
the list, the next thing we need to do

947
00:50:11,560 --> 00:50:14,880
is check if our value is there for
the pseudocode we wrote earlier.

948
00:50:14,880 --> 00:50:17,100
>> So how do we check if our value
is at the middle of the list?

949
00:50:17,100 --> 00:50:17,300
You.

950
00:50:17,300 --> 00:50:18,511
Why don't you do this?

951
00:50:18,511 --> 00:50:23,070
>> STUDENT: If our value's is
at the middle is equal to

952
00:50:23,070 --> 00:50:24,592
whatever we set the--

953
00:50:24,592 --> 00:50:26,190
I mean equal equal to--

954
00:50:26,190 --> 00:50:26,690
>> JASON HIRSCHHORN: It--

955
00:50:26,690 --> 00:50:27,940
OK.

956
00:50:27,940 --> 00:50:30,080

957
00:50:30,080 --> 00:50:32,170
>> STUDENT: I'm not sure what the
variable we're looking

958
00:50:32,170 --> 00:50:32,850
for though, is because--

959
00:50:32,850 --> 00:50:33,330
>> [INTERPOSING VOICES]

960
00:50:33,330 --> 00:50:34,520
>> STUDENT: [INAUDIBLE].

961
00:50:34,520 --> 00:50:35,060
>> JASON HIRSCHHORN: Exactly.

962
00:50:35,060 --> 00:50:37,260
Per the function declaration,
we're looking for a value.

963
00:50:37,260 --> 00:50:39,760
So we're searching for a value
in an array of values.

964
00:50:39,760 --> 00:50:41,080
So you're exactly right.

965
00:50:41,080 --> 00:50:45,040
You will do, if open paren value bracket
middle closed bracket equals

966
00:50:45,040 --> 00:50:49,930
equals value, and inside there
what do we need to do?

967
00:50:49,930 --> 00:50:51,230
If our value's there, what
do we need to do?

968
00:50:51,230 --> 00:50:51,420
>> [INTERPOSING VOICES]

969
00:50:51,420 --> 00:50:52,160
>> STUDENT: Return zero.

970
00:50:52,160 --> 00:50:53,070
>> JASON HIRSCHHORN: Return true.

971
00:50:53,070 --> 00:50:54,790
>> STUDENT: Return true.

972
00:50:54,790 --> 00:50:57,856
>> JASON HIRSCHHORN: Michael,
what does this line do?

973
00:50:57,856 --> 00:51:01,105
>> STUDENT: [INAUDIBLE] the program has run
its course, and that is over, and

974
00:51:01,105 --> 00:51:01,920
you've what you need to do?

975
00:51:01,920 --> 00:51:03,030
>> JASON HIRSCHHORN: The program or what?

976
00:51:03,030 --> 00:51:03,700
In this case?

977
00:51:03,700 --> 00:51:04,210
>> STUDENT: The function.

978
00:51:04,210 --> 00:51:05,170
>> JASON HIRSCHHORN: The function.

979
00:51:05,170 --> 00:51:08,420
And so, to return to whatever called
it and give it the value, true.

980
00:51:08,420 --> 00:51:09,890
Exactly right.

981
00:51:09,890 --> 00:51:10,170
Main.

982
00:51:10,170 --> 00:51:12,035
What's the return type
of main, Michael?

983
00:51:12,035 --> 00:51:16,480

984
00:51:16,480 --> 00:51:17,150
>> STUDENT: int, integer?

985
00:51:17,150 --> 00:51:18,080
>> JASON HIRSCHHORN: int, exactly.

986
00:51:18,080 --> 00:51:18,680
An integer.

987
00:51:18,680 --> 00:51:20,980
That was just a question to make sure
you guys have been on top of it.

988
00:51:20,980 --> 00:51:24,250
What does it usually return, if
all things are working well?

989
00:51:24,250 --> 00:51:24,520
>> STUDENT: Zero.

990
00:51:24,520 --> 00:51:24,820
>> JASON HIRSCHHORN: Zero.

991
00:51:24,820 --> 00:51:25,430
Exactly right.

992
00:51:25,430 --> 00:51:28,790
>> STUDENT: If this just returns true,
there's no information being given

993
00:51:28,790 --> 00:51:30,675
about what the--

994
00:51:30,675 --> 00:51:34,040
Oh, this is just saying that that
value's inside the array.

995
00:51:34,040 --> 00:51:35,350
>> JASON HIRSCHHORN: Exactly.

996
00:51:35,350 --> 00:51:38,080
This program is not giving information
of where exactly the value is.

997
00:51:38,080 --> 00:51:41,850
It's only saying, yes, we found
it, or no, we did not find it.

998
00:51:41,850 --> 00:51:42,990
So if number found, return true.

999
00:51:42,990 --> 00:51:45,500
Well, actually we just did that really
quickly with that one line of code.

1000
00:51:45,500 --> 00:51:47,500
So I'll move that line of pseudocode.

1001
00:51:47,500 --> 00:51:50,045
>> STUDENT: Don't we need
to change the array?

1002
00:51:50,045 --> 00:51:52,830
It should be values, not value, right?

1003
00:51:52,830 --> 00:51:53,430
>> JASON HIRSCHHORN: Sorry.

1004
00:51:53,430 --> 00:51:54,010
Thank you.

1005
00:51:54,010 --> 00:51:54,800
>> STUDENT: Yeah.

1006
00:51:54,800 --> 00:51:55,850
>> JASON HIRSCHHORN: This line
should be values.

1007
00:51:55,850 --> 00:51:57,150
Exactly right.

1008
00:51:57,150 --> 00:51:57,920
OK.

1009
00:51:57,920 --> 00:51:59,170
So we've looked at the middle list.

1010
00:51:59,170 --> 00:52:00,790
If number found return true.

1011
00:52:00,790 --> 00:52:04,470
Continuing on with our pseudocode, if
middle is greater, search left.

1012
00:52:04,470 --> 00:52:09,640
So I had in here, if number
higher, search left.

1013
00:52:09,640 --> 00:52:12,700

1014
00:52:12,700 --> 00:52:14,462
Constantine, can you give
me this line of code?

1015
00:52:14,462 --> 00:52:17,240

1016
00:52:17,240 --> 00:52:23,520
>> STUDENT: If value of middle--

1017
00:52:23,520 --> 00:52:24,890
>> JASON HIRSCHHORN: So if value--

1018
00:52:24,890 --> 00:52:28,890
if open paren values bracket
middle close bracket--

1019
00:52:28,890 --> 00:52:31,500
>> STUDENT: Is smaller than value?

1020
00:52:31,500 --> 00:52:32,760
>> JASON HIRSCHHORN: Is less than.

1021
00:52:32,760 --> 00:52:33,800
>> STUDENT: Less than value.

1022
00:52:33,800 --> 00:52:34,060
>> JASON HIRSCHHORN: Value.

1023
00:52:34,060 --> 00:52:35,310
Well, actually, you want to
check if the number--

1024
00:52:35,310 --> 00:52:38,310

1025
00:52:38,310 --> 00:52:38,490
Sorry.

1026
00:52:38,490 --> 00:52:39,140
This is a little confusing.

1027
00:52:39,140 --> 00:52:43,920
But else if the number in the
middle of list is greater.

1028
00:52:43,920 --> 00:52:45,170
>> STUDENT: Oh, OK.

1029
00:52:45,170 --> 00:52:49,800

1030
00:52:49,800 --> 00:52:50,410
>> JASON HIRSCHHORN: I'll change that.

1031
00:52:50,410 --> 00:52:55,060
Else if middle is higher, we
want to search left, OK?

1032
00:52:55,060 --> 00:52:57,310
And what do we do inside
this if condition?

1033
00:52:57,310 --> 00:53:03,660

1034
00:53:03,660 --> 00:53:07,510
>> STUDENT: Can I make a small change to
the condition, change it to else if?

1035
00:53:07,510 --> 00:53:08,380
>> JASON HIRSCHHORN: Else if?

1036
00:53:08,380 --> 00:53:09,270
OK.

1037
00:53:09,270 --> 00:53:12,840
So this code will execute
about the same.

1038
00:53:12,840 --> 00:53:18,620
But the nice thing about using if, else
if, else if or if, else if, else

1039
00:53:18,620 --> 00:53:22,320
means that only one of those is going to
be checked, not all three of them,

1040
00:53:22,320 --> 00:53:23,290
potentially.

1041
00:53:23,290 --> 00:53:25,530
And that makes it a little bit
nicer on the computer that's

1042
00:53:25,530 --> 00:53:26,670
running your program.

1043
00:53:26,670 --> 00:53:27,620
>> So [? Constantine, ?]

1044
00:53:27,620 --> 00:53:31,330
we're inside this line, else if values,
bracket middle close bracket

1045
00:53:31,330 --> 00:53:32,260
is greater than value.

1046
00:53:32,260 --> 00:53:33,150
What do we need to do?

1047
00:53:33,150 --> 00:53:33,970
We need to search the left.

1048
00:53:33,970 --> 00:53:35,220
How do we do that?

1049
00:53:35,220 --> 00:53:46,960

1050
00:53:46,960 --> 00:53:48,720
I'm going to give you a start.

1051
00:53:48,720 --> 00:53:52,210
>> We have these two things called
beginning and ending.

1052
00:53:52,210 --> 00:53:57,340
So what needs to happen
to the beginning?

1053
00:53:57,340 --> 00:53:59,640
If you want to search the left of the
list, we get our current beginning.

1054
00:53:59,640 --> 00:54:01,080
What do we need to do it?

1055
00:54:01,080 --> 00:54:04,220
>> STUDENT: We set the beginning
to middle plus 1.

1056
00:54:04,220 --> 00:54:05,120
>> JASON HIRSCHHORN: So if we're
searching the left?

1057
00:54:05,120 --> 00:54:06,250
>> STUDENT: Sorry, middle minus--

1058
00:54:06,250 --> 00:54:11,310
so the ending would be middle
minus 1 and beginning--

1059
00:54:11,310 --> 00:54:12,450
>> JASON HIRSCHHORN: And what
happens to the beginning?

1060
00:54:12,450 --> 00:54:13,210
>> STUDENT: It stays the same.

1061
00:54:13,210 --> 00:54:14,120
>> JASON HIRSCHHORN: So the
meaning stays the same.

1062
00:54:14,120 --> 00:54:16,040
If we're searching the left, we're
using the same beginning--

1063
00:54:16,040 --> 00:54:16,860
exactly right.

1064
00:54:16,860 --> 00:54:17,870
And the ending?

1065
00:54:17,870 --> 00:54:19,390
Sorry, what does the
ending equal again?

1066
00:54:19,390 --> 00:54:20,750
>> STUDENT: Middle minus 1.

1067
00:54:20,750 --> 00:54:21,620
>> JASON HIRSCHHORN: Middle minus 1.

1068
00:54:21,620 --> 00:54:23,470
Now, why minus 1, not just middle?

1069
00:54:23,470 --> 00:54:32,870

1070
00:54:32,870 --> 00:54:35,570
>> STUDENT: The middle is out of the
picture already, because we had

1071
00:54:35,570 --> 00:54:36,700
checked that it's out?

1072
00:54:36,700 --> 00:54:37,630
>> JASON HIRSCHHORN: That's
exactly right.

1073
00:54:37,630 --> 00:54:38,580
The middle is out of the picture.

1074
00:54:38,580 --> 00:54:39,800
We already checked the middle.

1075
00:54:39,800 --> 00:54:44,730
So we don't want "the middle," quote
unquote, to continue to be in the

1076
00:54:44,730 --> 00:54:46,110
array that we're looking.

1077
00:54:46,110 --> 00:54:47,670
So this is fantastic.

1078
00:54:47,670 --> 00:54:50,670
>> Else if values bracket middle is greater
than value ending equals

1079
00:54:50,670 --> 00:54:51,920
middle minus 1.

1080
00:54:51,920 --> 00:54:55,060

1081
00:54:55,060 --> 00:54:57,340
Jeff, what about this last line?

1082
00:54:57,340 --> 00:54:58,590
>> STUDENT: Else.

1083
00:54:58,590 --> 00:55:02,486

1084
00:55:02,486 --> 00:55:06,000
Values middle is less than value?

1085
00:55:06,000 --> 00:55:07,570
>> JASON HIRSCHHORN: We'll
you're giving me else.

1086
00:55:07,570 --> 00:55:09,310
So if you don't give me--

1087
00:55:09,310 --> 00:55:12,270
>> STUDENT: So then beginning
would be middle plus 1.

1088
00:55:12,270 --> 00:55:16,100

1089
00:55:16,100 --> 00:55:19,070
>> JASON HIRSCHHORN: Beginning equals
middle plus 1, again, for the same

1090
00:55:19,070 --> 00:55:20,820
reason that Constantine
gave us earlier.

1091
00:55:20,820 --> 00:55:24,280
And at the end, who hasn't given
me a line of code yet?

1092
00:55:24,280 --> 00:55:26,600
Return false, Aleha, what
do we write here?

1093
00:55:26,600 --> 00:55:28,590
>> STUDENT: Return false.

1094
00:55:28,590 --> 00:55:29,320
>> JASON HIRSCHHORN: Return false.

1095
00:55:29,320 --> 00:55:33,340
And we need to do that, because if we
don't find it, we need to say we

1096
00:55:33,340 --> 00:55:34,080
didn't find it.

1097
00:55:34,080 --> 00:55:36,270
And we said we're going to return a
bool, so we definitely have to return

1098
00:55:36,270 --> 00:55:38,150
a bool somewhere.

1099
00:55:38,150 --> 00:55:42,590
>> So let's run this code.

1100
00:55:42,590 --> 00:55:44,520
I'm actually going to--

1101
00:55:44,520 --> 00:55:45,930
so we're in the terminal.

1102
00:55:45,930 --> 00:55:47,230
We'll clear our window.

1103
00:55:47,230 --> 00:55:49,270
Let's Make All.

1104
00:55:49,270 --> 00:55:50,340
We found there's one error.

1105
00:55:50,340 --> 00:55:54,280
There's an error on line 15, expected
semicolon at the end of the

1106
00:55:54,280 --> 00:55:54,890
declaration.

1107
00:55:54,890 --> 00:55:56,454
So what did I forget?

1108
00:55:56,454 --> 00:55:57,230
>> STUDENT: Semicolon.

1109
00:55:57,230 --> 00:56:00,200
>> JASON HIRSCHHORN: Semicolon
right up here.

1110
00:56:00,200 --> 00:56:00,950
I think that was Tom's code.

1111
00:56:00,950 --> 00:56:01,870
So Tom, [INAUDIBLE].

1112
00:56:01,870 --> 00:56:03,120
Just kidding.

1113
00:56:03,120 --> 00:56:05,010

1114
00:56:05,010 --> 00:56:07,310
Let's do Make All again.

1115
00:56:07,310 --> 00:56:10,180
>> STUDENT: What Dropbox directory
should we be in for this?

1116
00:56:10,180 --> 00:56:11,345
>> JASON HIRSCHHORN: So you can
just watch for this bit.

1117
00:56:11,345 --> 00:56:16,380
But again, if you wanted to move this
code into your pset3 directory to try

1118
00:56:16,380 --> 00:56:17,050
it out, that's what I did.

1119
00:56:17,050 --> 00:56:18,600
If you'll notice here--
sorry, good question.

1120
00:56:18,600 --> 00:56:19,460
>> [? LS, ?]

1121
00:56:19,460 --> 00:56:24,700
I have in here the find.c code
from this week's distro code.

1122
00:56:24,700 --> 00:56:26,300
I have helpers.h.

1123
00:56:26,300 --> 00:56:30,010
I have a Make file that I actually
edited a bit to include these new

1124
00:56:30,010 --> 00:56:30,710
files we're writing.

1125
00:56:30,710 --> 00:56:34,120
All of that code will be available, not
the distribution code, but the new

1126
00:56:34,120 --> 00:56:39,510
Make file, the new helpers.h file will
be available online for download.

1127
00:56:39,510 --> 00:56:41,800
Again, so those are the
extra codes we have.

1128
00:56:41,800 --> 00:56:46,130
>> So make all, per this line, makes find,
binary, bubble selection-- makes

1129
00:56:46,130 --> 00:56:50,930
all three of them and compiles into
this executable code find.

1130
00:56:50,930 --> 00:56:54,090
So generally, we don't want
to straight to check50.

1131
00:56:54,090 --> 00:56:57,580
We want to run some tests on our own.

1132
00:56:57,580 --> 00:57:11,750
But just so we can expedite this a bit,
check50 2013 pset3.find will pass

1133
00:57:11,750 --> 00:57:14,630
in helpers.c-- my bad.

1134
00:57:14,630 --> 00:57:16,050
>> I don't have that right now.

1135
00:57:16,050 --> 00:57:20,670
So we're actually going to
run the code for real.

1136
00:57:20,670 --> 00:57:23,570
Usage.find/, you know what that means?

1137
00:57:23,570 --> 00:57:25,970
>> STUDENT: You need a second
command line on it.

1138
00:57:25,970 --> 00:57:26,980
>> JASON HIRSCHHORN: I need
a second command line.

1139
00:57:26,980 --> 00:57:30,640
And per the specification, I need
to enter what we're looking for.

1140
00:57:30,640 --> 00:57:33,750
So let's look for 42.

1141
00:57:33,750 --> 00:57:37,030
We'll keep it in sorted, because we
haven't written a sort function yet--

1142
00:57:37,030 --> 00:57:41,830
42, 43, 44.

1143
00:57:41,830 --> 00:57:46,240
>> And Control D didn't find the
needle in the haystack.

1144
00:57:46,240 --> 00:57:46,505
That's bad.

1145
00:57:46,505 --> 00:57:47,200
It's definitely there.

1146
00:57:47,200 --> 00:57:48,090
Let's try something else.

1147
00:57:48,090 --> 00:57:49,860
Maybe it's because I put
it at the beginning.

1148
00:57:49,860 --> 00:57:54,490
>> Let's do 41, 42, 43.

1149
00:57:54,490 --> 00:57:55,012
There we go.

1150
00:57:55,012 --> 00:57:56,400
It found it.

1151
00:57:56,400 --> 00:58:00,040
Let's put it at the end now, just
so we can be thorough--

1152
00:58:00,040 --> 00:58:03,580
40, 41, 42.

1153
00:58:03,580 --> 00:58:05,760
Didn't find the needle.

1154
00:58:05,760 --> 00:58:07,550
So I mentioned this earlier.

1155
00:58:07,550 --> 00:58:08,980
Unfortunately, I knew this
was going to happen.

1156
00:58:08,980 --> 00:58:11,490
>> But for pedagogical purposes,
it's good to explore it.

1157
00:58:11,490 --> 00:58:12,990
It doesn't work.

1158
00:58:12,990 --> 00:58:16,020
For some reason, it can't find it.

1159
00:58:16,020 --> 00:58:18,970
We know what's in there, but
we aren't finding it.

1160
00:58:18,970 --> 00:58:24,140
So one thing we could do is go through
GDB to find it, but does anybody,

1161
00:58:24,140 --> 00:58:27,850
without going through GDB, have a
sense of where we screwed up?

1162
00:58:27,850 --> 00:58:28,480
[? Madu? ?]

1163
00:58:28,480 --> 00:58:30,960
>> STUDENT: I think it might be when ending
is equal to beginning, and it's

1164
00:58:30,960 --> 00:58:33,090
just a one-element list.

1165
00:58:33,090 --> 00:58:35,560
Then it just ignores it instead
of actually checking it.

1166
00:58:35,560 --> 00:58:36,940
>> JASON HIRSCHHORN: That's
exactly right.

1167
00:58:36,940 --> 00:58:41,110
When ending equals beginning, do we
still have an element in our list?

1168
00:58:41,110 --> 00:58:42,480
>> STUDENT: Yes.

1169
00:58:42,480 --> 00:58:45,450
>> JASON HIRSCHHORN: Yes, in fact, we
have one and only one element.

1170
00:58:45,450 --> 00:58:50,500
And that will most likely happen when,
per the code we tested, we are at the

1171
00:58:50,500 --> 00:58:54,640
front of the haystack or at
the end of the haystack.

1172
00:58:54,640 --> 00:58:56,000
That's where beginning and
ending is going to equal

1173
00:58:56,000 --> 00:58:57,820
one, with binary search.

1174
00:58:57,820 --> 00:59:01,440
So in those two cases it didn't work,
because ending was equal to beginning.

1175
00:59:01,440 --> 00:59:06,030
>> But if ending is equal to beginning,
does this while loop execute?

1176
00:59:06,030 --> 00:59:06,390
It doesn't.

1177
00:59:06,390 --> 00:59:08,660
And we could have checked
that again through GDB.

1178
00:59:08,660 --> 00:59:14,000
So how can we fix this code, because
when while ending is equal to

1179
00:59:14,000 --> 00:59:16,070
beginning, we also want this
while loop to run.

1180
00:59:16,070 --> 00:59:18,620
>> So what fix can we make to line 18?

1181
00:59:18,620 --> 00:59:21,060
>> STUDENT: [INAUDIBLE] is greater
than or equal to.

1182
00:59:21,060 --> 00:59:21,700
>> JASON HIRSCHHORN: Exactly right.

1183
00:59:21,700 --> 00:59:24,600
While ending is greater than
or equal to beginning.

1184
00:59:24,600 --> 00:59:27,300
So now, we make sure to get that
corner case at the end.

1185
00:59:27,300 --> 00:59:27,870
And let's see.

1186
00:59:27,870 --> 00:59:29,560
Let's run this one more time.

1187
00:59:29,560 --> 00:59:31,266
>> Let's make all.

1188
00:59:31,266 --> 00:59:33,910
Again, you'll have to just
follow along here.

1189
00:59:33,910 --> 00:59:36,280
Find 41 this time.

1190
00:59:36,280 --> 00:59:37,360
Just keep it consistent.

1191
00:59:37,360 --> 00:59:38,210
>> Find 42.

1192
00:59:38,210 --> 00:59:38,930
Let's put it at the beginning--

1193
00:59:38,930 --> 00:59:41,630
42, 43, 44.

1194
00:59:41,630 --> 00:59:42,860
We found it.

1195
00:59:42,860 --> 00:59:47,710
So that was indeed the change
we needed to make.

1196
00:59:47,710 --> 00:59:51,090
>> That was a lot of coding we
just did, binary search.

1197
00:59:51,090 --> 00:59:55,760
Does anybody have any questions before
I move on into lines we wrote in

1198
00:59:55,760 --> 00:59:58,750
binary search or how we figured
out what we did figure out?

1199
00:59:58,750 --> 01:00:01,900

1200
01:00:01,900 --> 01:00:06,270
Before we move on, I also want to point
out that by and large, we mapped

1201
01:00:06,270 --> 01:00:09,300
our pseudo-code one to
one onto our code.

1202
01:00:09,300 --> 01:00:11,550
>> We did have that tricky thing
to figure out with the

1203
01:00:11,550 --> 01:00:12,890
beginning and ending.

1204
01:00:12,890 --> 01:00:17,380
But had you not figured that out, you
would have written pretty much the

1205
01:00:17,380 --> 01:00:20,740
identical code, save for
those top two lines.

1206
01:00:20,740 --> 01:00:23,380
And then you would have realized when
you made it in checks and cases that

1207
01:00:23,380 --> 01:00:24,840
you need something else.

1208
01:00:24,840 --> 01:00:28,510
So even if you had followed our
pseudo-code line to line, you would've

1209
01:00:28,510 --> 01:00:31,130
gotten all but two lines of
code you needed to write.

1210
01:00:31,130 --> 01:00:33,900
>> And I'd be willing to bet that you guys
would have all figured that out

1211
01:00:33,900 --> 01:00:37,940
pretty quickly, that you needed to put
some sort of marker in there to figure

1212
01:00:37,940 --> 01:00:39,190
out where you were.

1213
01:00:39,190 --> 01:00:41,540

1214
01:00:41,540 --> 01:00:44,550
That again, is the power of doing
pseudo-code ahead of time.

1215
01:00:44,550 --> 01:00:47,310
So we can do the logic first, and then
we can worry about the syntax.

1216
01:00:47,310 --> 01:00:51,470
>> Had we been confused about the logic
while trying to write this code in C,

1217
01:00:51,470 --> 01:00:53,110
we would have gotten all messed up.

1218
01:00:53,110 --> 01:00:56,340
And then we'd be asking questions about
logic and syntax and meshing

1219
01:00:56,340 --> 01:00:57,320
them all together.

1220
01:00:57,320 --> 01:01:02,170
And we would have gotten lost
in what can quickly become a

1221
01:01:02,170 --> 01:01:04,000
very difficult problem.

1222
01:01:04,000 --> 01:01:08,680
So let's move on now
to selection sort.

1223
01:01:08,680 --> 01:01:10,760
>> We have 20 minutes left.

1224
01:01:10,760 --> 01:01:14,130
So I have a feeling we won't be able to
get through all of selection sort

1225
01:01:14,130 --> 01:01:15,940
and bubble sort.

1226
01:01:15,940 --> 01:01:20,670
But let us at least attempt
to finish selection sort.

1227
01:01:20,670 --> 01:01:23,540
So implement selection sort using the
following function declaration.

1228
01:01:23,540 --> 01:01:27,530
>> Again, this is taken from the
problem set specification.

1229
01:01:27,530 --> 01:01:31,560
Int values is brackets, is
an array of integers.

1230
01:01:31,560 --> 01:01:33,490
And int.n is the size of that array.

1231
01:01:33,490 --> 01:01:36,840
Selection sort is going
to sort this array.

1232
01:01:36,840 --> 01:01:43,580
>> So per our mental model of selection
sort, we pull the--

1233
01:01:43,580 --> 01:01:47,720
first, we go through the list the first
time, find the smallest number,

1234
01:01:47,720 --> 01:01:52,860
put it at the beginning, find the second
smallest number, put it in the

1235
01:01:52,860 --> 01:01:56,380
second position if we want to
sort in ascending order.

1236
01:01:56,380 --> 01:01:58,440
I'm not forcing you to write
pseudo-code right now.

1237
01:01:58,440 --> 01:02:01,350
>> But before we do the code as a class in
five minutes, we are going to write

1238
01:02:01,350 --> 01:02:03,550
pseudo-code so we have some sense
of where we're going.

1239
01:02:03,550 --> 01:02:05,630
So attempt to write pseudo-code
on your own.

1240
01:02:05,630 --> 01:02:08,610
And then attempt to turn that
pseudo-code into code.

1241
01:02:08,610 --> 01:02:10,740
We will do that as a group
in five minutes.

1242
01:02:10,740 --> 01:02:32,560

1243
01:02:32,560 --> 01:02:33,895
>> And of course, let me know if
you have any questions.

1244
01:02:33,895 --> 01:03:56,738

1245
01:03:56,738 --> 01:03:58,230
>> STUDENT: That it?

1246
01:03:58,230 --> 01:04:00,280
>> JASON HIRSCHHORN: See how far you
can get in two more minutes.

1247
01:04:00,280 --> 01:04:01,790
I understand you won't
be able to finish.

1248
01:04:01,790 --> 01:04:03,050
But we will go over this as a group.

1249
01:04:03,050 --> 01:04:57,830

1250
01:04:57,830 --> 01:05:00,630
>> You're all coding so [INAUDIBLE], so I'm
sorry to pause what you're doing.

1251
01:05:00,630 --> 01:05:02,530
But let's go through this as a group.

1252
01:05:02,530 --> 01:05:07,590
And again, binary search, you all give
me one if not more lines of code.

1253
01:05:07,590 --> 01:05:08,530
Thank you for that.

1254
01:05:08,530 --> 01:05:11,730
We're going to do the same thing
here, code together as a group.

1255
01:05:11,730 --> 01:05:15,170
>> So selection sort-- let's write
some quick pseudo-code.

1256
01:05:15,170 --> 01:05:20,380
Per mental model, can someone give me
the first line of pseudo-code, please?

1257
01:05:20,380 --> 01:05:23,000

1258
01:05:23,000 --> 01:05:24,270
What do I want to do?

1259
01:05:24,270 --> 01:05:27,070
>> STUDENT: While the list
is out of order.

1260
01:05:27,070 --> 01:05:30,630
>> JASON HIRSCHHORN: OK, while
the list is out of order.

1261
01:05:30,630 --> 01:05:33,540
And what do you mean "out of order?"

1262
01:05:33,540 --> 01:05:34,960
>> STUDENT: While [INAUDIBLE]

1263
01:05:34,960 --> 01:05:36,210
hasn't been sorted.

1264
01:05:36,210 --> 01:05:38,460

1265
01:05:38,460 --> 01:05:40,290
>> JASON HIRSCHHORN: While the list
is out of order, what do we do?

1266
01:05:40,290 --> 01:05:44,200
Give me the second line,
please, Marcus.

1267
01:05:44,200 --> 01:05:47,186
>> STUDENT: So find the next
smallest number.

1268
01:05:47,186 --> 01:05:49,000
This will be indented.

1269
01:05:49,000 --> 01:05:55,140
>> JASON HIRSCHHORN: So find the
next smallest number.

1270
01:05:55,140 --> 01:05:56,460
And then somebody else?

1271
01:05:56,460 --> 01:06:01,030
Once we find the next smallest
number, what do we do?

1272
01:06:01,030 --> 01:06:03,010
I'm going to say find
the smallest number.

1273
01:06:03,010 --> 01:06:04,820
That's what we want to do.

1274
01:06:04,820 --> 01:06:06,210
>> So find the smallest number.

1275
01:06:06,210 --> 01:06:08,061
Then what do we do?

1276
01:06:08,061 --> 01:06:09,480
>> STUDENT: [INAUDIBLE] to beginning.

1277
01:06:09,480 --> 01:06:10,680
>> JASON HIRSCHHORN: Sorry?

1278
01:06:10,680 --> 01:06:12,700
>> STUDENT: Place it in the
beginning of the list.

1279
01:06:12,700 --> 01:06:18,540
>> JASON HIRSCHHORN: So place it in
the beginning of the list.

1280
01:06:18,540 --> 01:06:20,140
And what do we do to the thing
that was in the beginning

1281
01:06:20,140 --> 01:06:20,830
of the list, right?

1282
01:06:20,830 --> 01:06:21,910
We're overwriting something.

1283
01:06:21,910 --> 01:06:23,130
So where do we put that?

1284
01:06:23,130 --> 01:06:24,120
Yeah, Anna?

1285
01:06:24,120 --> 01:06:25,520
>> STUDENT: Where the smallest
number was?

1286
01:06:25,520 --> 01:06:32,530
>> JASON HIRSHHORN: So put the beginning
of the list where the

1287
01:06:32,530 --> 01:06:35,180
smallest number was.

1288
01:06:35,180 --> 01:06:38,510
So while the list is out of order, find
the smallest number, place it in

1289
01:06:38,510 --> 01:06:40,630
the beginning of the list, put the
beginning of the list where the

1290
01:06:40,630 --> 01:06:42,900
smallest number was.

1291
01:06:42,900 --> 01:06:45,780
Marcus, can you rephrase this line
while the list is out of order?

1292
01:06:45,780 --> 01:06:51,160

1293
01:06:51,160 --> 01:06:53,900
>> STUDENT: While the numbers
haven't been sorted?

1294
01:06:53,900 --> 01:06:55,920
>> JASON HIRSHHORN: OK, so in order to
know that the numbers haven't been

1295
01:06:55,920 --> 01:06:58,670
sorted, what do we need to do?

1296
01:06:58,670 --> 01:07:00,640
How much do we need to
go through this list?

1297
01:07:00,640 --> 01:07:09,650
>> STUDENT: So I guess a for loop, or
while, while numbers checked is less

1298
01:07:09,650 --> 01:07:11,900
than the length of the list?

1299
01:07:11,900 --> 01:07:13,160
>> JASON HIRSHHORN: OK, that's good.

1300
01:07:13,160 --> 01:07:15,000
I think I misphrased
my question poorly.

1301
01:07:15,000 --> 01:07:15,990
I was just trying to get at
we're going to have to go

1302
01:07:15,990 --> 01:07:17,580
through the whole list.

1303
01:07:17,580 --> 01:07:20,490
So while the list is out of order,
for me, is hard to map on.

1304
01:07:20,490 --> 01:07:24,940
But basically, that's how
I think about this.

1305
01:07:24,940 --> 01:07:28,880
Go through the entire list, find the
smallest number, place it in the

1306
01:07:28,880 --> 01:07:30,130
beginning-- actually, you're right.

1307
01:07:30,130 --> 01:07:31,380
Let's put them both.

1308
01:07:31,380 --> 01:07:33,470

1309
01:07:33,470 --> 01:07:39,050
>> So while the list is out of order, we
need to go through the entire list

1310
01:07:39,050 --> 01:07:42,250
once, find the smallest number, place
it in the beginning of the list, put

1311
01:07:42,250 --> 01:07:45,430
the beginning of the list where the
smallest number was, and then if the

1312
01:07:45,430 --> 01:07:47,460
list is still out of order, we've
got to go through this

1313
01:07:47,460 --> 01:07:48,620
process again, right?

1314
01:07:48,620 --> 01:07:51,610
That's why selection sort, Big-O runtime
of selection sort, anyone?

1315
01:07:51,610 --> 01:07:52,830
>> STUDENT: n squared.

1316
01:07:52,830 --> 01:07:53,590
>> JASON HIRSHHORN: n squared.

1317
01:07:53,590 --> 01:07:57,040
Because like Marcus and I just realized
here, we're going to have to

1318
01:07:57,040 --> 01:08:00,310
go through the list list
number of times.

1319
01:08:00,310 --> 01:08:03,420
So going through something of
length n n number of times

1320
01:08:03,420 --> 01:08:04,990
is in fact n squared.

1321
01:08:04,990 --> 01:08:08,100
>> So this is our pseudocode.

1322
01:08:08,100 --> 01:08:09,360
This looks very good.

1323
01:08:09,360 --> 01:08:11,870
Does anybody have any questions
about the pseudocode?

1324
01:08:11,870 --> 01:08:14,440
Because actually selection sort should
probably come one to one, code from

1325
01:08:14,440 --> 01:08:14,980
pseudocode.

1326
01:08:14,980 --> 01:08:17,569
So any questions about the
logic of the pseudocode?

1327
01:08:17,569 --> 01:08:18,819
Please ask it now.

1328
01:08:18,819 --> 01:08:22,609

1329
01:08:22,609 --> 01:08:25,379
>> Selection sort-- while the list is out
of order, we're going to go through it

1330
01:08:25,379 --> 01:08:27,529
and find the smallest each time
and put it in the front.

1331
01:08:27,529 --> 01:08:33,470
So while the list is out of order, can
somebody give me that line of code who

1332
01:08:33,470 --> 01:08:39,689
has not given me a line
of code yet, please?

1333
01:08:39,689 --> 01:08:40,939
It sounds like a what?

1334
01:08:40,939 --> 01:08:43,669

1335
01:08:43,669 --> 01:08:44,649
>> STUDENT: That's a for loop.

1336
01:08:44,649 --> 01:08:45,830
>> JASON HIRSHHORN: It sounds
like a for loop.

1337
01:08:45,830 --> 01:08:47,653
OK, can you give me the for loop?

1338
01:08:47,653 --> 01:08:48,925
For--

1339
01:08:48,925 --> 01:08:50,219
>> STUDENT: i Equals 0.

1340
01:08:50,219 --> 01:08:52,705
>> JASON HIRSHHORN: i or--

1341
01:08:52,705 --> 01:08:55,111
what are we missing?

1342
01:08:55,111 --> 01:08:56,819
What goes right here?

1343
01:08:56,819 --> 01:08:57,550
>> STUDENT: Int.

1344
01:08:57,550 --> 01:08:59,270
>> JASON HIRSHHORN: Exactly.

1345
01:08:59,270 --> 01:09:02,590
(int i = 0;--

1346
01:09:02,590 --> 01:09:07,843
>> STUDENT: i < n; i++).

1347
01:09:07,843 --> 01:09:09,319
>> JASON HIRSHHORN: Nailed it, Jeff.

1348
01:09:09,319 --> 01:09:10,660
We're going through the list, right?

1349
01:09:10,660 --> 01:09:11,880
We've seen that code before.

1350
01:09:11,880 --> 01:09:12,850
Perfect.

1351
01:09:12,850 --> 01:09:14,790
So let's put our curly braces here.

1352
01:09:14,790 --> 01:09:17,859
I'm going to put some
curly braces here.

1353
01:09:17,859 --> 01:09:21,660
>> So while it's 0, we need to go
through the entire list.

1354
01:09:21,660 --> 01:09:26,612
So each time we go through the list,
what do we want to keep track of?

1355
01:09:26,612 --> 01:09:28,260
>> STUDENT: If any swaps are made.

1356
01:09:28,260 --> 01:09:29,069
>> JASON HIRSHHORN: Find
the smallest number.

1357
01:09:29,069 --> 01:09:31,479
So we should probably keep track of
the smallest number each time.

1358
01:09:31,479 --> 01:09:34,590
So line can I do to keep track
of the smallest number?

1359
01:09:34,590 --> 01:09:37,720
Aleha, how can I keep
track of something?

1360
01:09:37,720 --> 01:09:38,460
>> STUDENT: Start a new variable.

1361
01:09:38,460 --> 01:09:39,390
>> JASON HIRSHHORN: Start a new variable.

1362
01:09:39,390 --> 01:09:40,069
So let's create a variable.

1363
01:09:40,069 --> 01:09:41,830
What type?

1364
01:09:41,830 --> 01:09:42,930
>> STUDENT: Int.

1365
01:09:42,930 --> 01:09:43,710
>> JASON HIRSHHORN: Int.

1366
01:09:43,710 --> 01:09:44,939
Let's call it the smallest.

1367
01:09:44,939 --> 01:09:47,600
And what does it equal when
we're just starting out?

1368
01:09:47,600 --> 01:09:48,910
We haven't gone through the list yet.

1369
01:09:48,910 --> 01:09:50,540
We're at the first part of the
list our first time through.

1370
01:09:50,540 --> 01:09:51,930
What does it equal, the
smallest number?

1371
01:09:51,930 --> 01:09:54,140
>> STUDENT: Values i.

1372
01:09:54,140 --> 01:09:54,900
>> JASON HIRSHHORN: Values i.

1373
01:09:54,900 --> 01:09:56,980
That sounds exactly right, right?

1374
01:09:56,980 --> 01:09:59,590
The smallest number at the beginning
is where we are.

1375
01:09:59,590 --> 01:10:01,960
So now we have our smallest, and we need
to go through the entire list and

1376
01:10:01,960 --> 01:10:05,080
compare this smallest
to everything else.

1377
01:10:05,080 --> 01:10:08,150
So do we go through the list again?

1378
01:10:08,150 --> 01:10:08,630
Michael?

1379
01:10:08,630 --> 01:10:10,000
>> STUDENT: You need to make
another for loop.

1380
01:10:10,000 --> 01:10:10,383
>> JASON HIRSHHORN: Another for loop.

1381
01:10:10,383 --> 01:10:11,276
Let's do it.

1382
01:10:11,276 --> 01:10:12,540
Give me some code.

1383
01:10:12,540 --> 01:10:13,790
>> STUDENT: For loop--

1384
01:10:13,790 --> 01:10:16,750

1385
01:10:16,750 --> 01:10:19,470
for the smallest--

1386
01:10:19,470 --> 01:10:23,040

1387
01:10:23,040 --> 01:10:25,770
just int j, could you say?

1388
01:10:25,770 --> 01:10:31,150
= 0; such that--

1389
01:10:31,150 --> 01:10:34,014

1390
01:10:34,014 --> 01:10:35,710
>> JASON HIRSHHORN: Well, if we want
to go through the entire list--

1391
01:10:35,710 --> 01:10:37,847
>> STUDENT: j < n, j++).

1392
01:10:37,847 --> 01:10:42,140

1393
01:10:42,140 --> 01:10:42,405
>> JASON HIRSHHORN: Fantastic.

1394
01:10:42,405 --> 01:10:46,100
We're going to go through
the for loop once again.

1395
01:10:46,100 --> 01:10:51,380
And how do we find the
smallest number?

1396
01:10:51,380 --> 01:10:52,630
Tom?

1397
01:10:52,630 --> 01:10:54,570

1398
01:10:54,570 --> 01:11:00,520
We have the current smallest number,
so how do we find the new smallest?

1399
01:11:00,520 --> 01:11:07,200
>> STUDENT: We can check if the smallest
number we have is greater than

1400
01:11:07,200 --> 01:11:09,040
values bracket j.

1401
01:11:09,040 --> 01:11:14,740
>> JASON HIRSHHORN: So if smallest is
greater than values bracket j.

1402
01:11:14,740 --> 01:11:19,350
So if our current smallest
is greater than--

1403
01:11:19,350 --> 01:11:21,770
I'm going to move these two lines
of code out there for a second.

1404
01:11:21,770 --> 01:11:26,010
Because before we do any swapping, we
need to go through the entire list.

1405
01:11:26,010 --> 01:11:28,880
So this pseudocode should actually
be outside that inner for loop.

1406
01:11:28,880 --> 01:11:30,390
So go through the entire list.

1407
01:11:30,390 --> 01:11:34,520
If smallest is greater than
values j then what?

1408
01:11:34,520 --> 01:11:37,830
>> STUDENT: Then smallest
equals values j.

1409
01:11:37,830 --> 01:11:41,190

1410
01:11:41,190 --> 01:11:42,600
>> JASON HIRSHHORN: Fantastic.

1411
01:11:42,600 --> 01:11:44,580
One quick question--

1412
01:11:44,580 --> 01:11:47,236
the first time we go through this loop,
i's going to equal 0, j's going

1413
01:11:47,236 --> 01:11:50,710
to equal 0 once we get in here.

1414
01:11:50,710 --> 01:11:52,410
So we're going to be comparing
a number to itself.

1415
01:11:52,410 --> 01:11:53,660
Is that efficient?

1416
01:11:53,660 --> 01:11:57,260

1417
01:11:57,260 --> 01:11:58,390
No, it's not really efficient.

1418
01:11:58,390 --> 01:12:02,915
So does our j need to go
from 0 to n each time?

1419
01:12:02,915 --> 01:12:06,310
Do we always need to check
through the entire list?

1420
01:12:06,310 --> 01:12:06,520
[INAUDIBLE]?

1421
01:12:06,520 --> 01:12:07,564
>> STUDENT: Start with i instead.

1422
01:12:07,564 --> 01:12:09,405
>> JASON HIRSHHORN: j can
start with what?

1423
01:12:09,405 --> 01:12:09,990
>> STUDENT: i.

1424
01:12:09,990 --> 01:12:13,040
>> JASON HIRSHHORN: j can start with i.

1425
01:12:13,040 --> 01:12:18,840
So now we compare starting
with the one we're on.

1426
01:12:18,840 --> 01:12:21,020
But even then, is that as
efficient as possible?

1427
01:12:21,020 --> 01:12:22,320
>> STUDENT: i + 1.

1428
01:12:22,320 --> 01:12:25,420
>> JASON HIRSHHORN: i + 1 seems to be
the most efficient, because we

1429
01:12:25,420 --> 01:12:26,120
already have i.

1430
01:12:26,120 --> 01:12:28,100
We're stating that as the
smallest in line 15.

1431
01:12:28,100 --> 01:12:29,350
We're going to start with the
next one automatically.

1432
01:12:29,350 --> 01:12:34,470

1433
01:12:34,470 --> 01:12:38,540
So we go through the for loop.

1434
01:12:38,540 --> 01:12:39,620
We'll go through each time.

1435
01:12:39,620 --> 01:12:40,860
We'll go through a number of times.

1436
01:12:40,860 --> 01:12:42,860
Now we've gotten through
this inner for loop.

1437
01:12:42,860 --> 01:12:44,350
We have the smallest value saves.

1438
01:12:44,350 --> 01:12:46,045
We need to place it at the
beginning of the list.

1439
01:12:46,045 --> 01:12:48,390
So how do I place it at the
beginning of the list?

1440
01:12:48,390 --> 01:12:51,290

1441
01:12:51,290 --> 01:12:55,926
What is the variable that refers
to the beginning of the list?

1442
01:12:55,926 --> 01:13:00,500
We're in this outside for loop,
so what refers to the

1443
01:13:00,500 --> 01:13:01,280
beginning of the list?

1444
01:13:01,280 --> 01:13:02,880
>> STUDENT: Values i.

1445
01:13:02,880 --> 01:13:03,510
>> JASON HIRSHHORN: Exactly right.

1446
01:13:03,510 --> 01:13:04,650
Values i is the beginning of the--

1447
01:13:04,650 --> 01:13:06,320
or sorry, not the beginning.

1448
01:13:06,320 --> 01:13:07,090
That was confusing.

1449
01:13:07,090 --> 01:13:11,620
It's where we are in the beginning of
the unsorted portion of the list.

1450
01:13:11,620 --> 01:13:12,800
So values i.

1451
01:13:12,800 --> 01:13:14,050
And what does that equal?

1452
01:13:14,050 --> 01:13:15,925

1453
01:13:15,925 --> 01:13:17,326
>> STUDENT: Smallest.

1454
01:13:17,326 --> 01:13:18,862
>> JASON HIRSHHORN: Values i equals what?

1455
01:13:18,862 --> 01:13:19,310
>> STUDENT: Smallest.

1456
01:13:19,310 --> 01:13:20,030
>> JASON HIRSHHORN: Smallest.

1457
01:13:20,030 --> 01:13:20,980
Exactly right.

1458
01:13:20,980 --> 01:13:23,510
So we're placing it at the beginning
of the list, and now we need to put

1459
01:13:23,510 --> 01:13:25,710
the beginning of the list where
the smallest number was.

1460
01:13:25,710 --> 01:13:29,700
So how do I write where the
smallest number was?

1461
01:13:29,700 --> 01:13:31,670
Values of what?

1462
01:13:31,670 --> 01:13:33,170
>> STUDENT: 0.

1463
01:13:33,170 --> 01:13:34,090
>> JASON HIRSHHORN: The small
number's at 0?

1464
01:13:34,090 --> 01:13:35,340
>> STUDENT: Yeah.

1465
01:13:35,340 --> 01:13:38,680

1466
01:13:38,680 --> 01:13:39,910
>> JASON HIRSHHORN: What if the smallest
number was at the end of

1467
01:13:39,910 --> 01:13:40,860
this unsorted list?

1468
01:13:40,860 --> 01:13:42,460
>> STUDENT: Sorry, what was the question?

1469
01:13:42,460 --> 01:13:44,020
>> JASON HIRSHHORN: Where is
the smallest number?

1470
01:13:44,020 --> 01:13:46,940
We took the smallest and put it at the
beginning, with this line right here.

1471
01:13:46,940 --> 01:13:48,987
>> STUDENT: It should have
been stored in some--

1472
01:13:48,987 --> 01:13:50,510
>> STUDENT: Values j.

1473
01:13:50,510 --> 01:13:51,520
>> JASON HIRSHHORN: Well, it's
not necessarily values j.

1474
01:13:51,520 --> 01:13:54,100
It doesn't even exist at this point.

1475
01:13:54,100 --> 01:13:55,960
>> STUDENT: You have to declare
a variable earlier and

1476
01:13:55,960 --> 01:13:58,230
then assign it to--

1477
01:13:58,230 --> 01:14:01,150
when you find the smallest number,
assign the index of that number to

1478
01:14:01,150 --> 01:14:02,480
some variable or something like that.

1479
01:14:02,480 --> 01:14:04,790
>> JASON HIRSHHORN: So can
you say that again?

1480
01:14:04,790 --> 01:14:08,390
>> STUDENT: So where you declared int
smallest, you should also declare int

1481
01:14:08,390 --> 01:14:10,750
smallest index = i, or
something like that.

1482
01:14:10,750 --> 01:14:13,280
>> JASON HIRSHHORN: So where I do int
smallest, I should not only keep track

1483
01:14:13,280 --> 01:14:16,150
of the value but the location.

1484
01:14:16,150 --> 01:14:20,850
int smallest_location = in this
case, we'll just do i.

1485
01:14:20,850 --> 01:14:22,390
We need to know where it is.

1486
01:14:22,390 --> 01:14:26,820
We got to the end of the code, and we
realized we had no idea where it was.

1487
01:14:26,820 --> 01:14:29,810
And so again, we are mapping
this on one to one.

1488
01:14:29,810 --> 01:14:32,890
You guys coding this on your own will
probably get to the same problem.

1489
01:14:32,890 --> 01:14:34,130
How the heck do I find it?

1490
01:14:34,130 --> 01:14:36,720
And then you realize, wait, I
need to keep track of that.

1491
01:14:36,720 --> 01:14:38,500
>> So if smallest is greater
than values j.

1492
01:14:38,500 --> 01:14:39,740
We set smallest equals to values j.

1493
01:14:39,740 --> 01:14:42,090
What else do we need to change?

1494
01:14:42,090 --> 01:14:43,710
Constantin, what else do
we need to change?

1495
01:14:43,710 --> 01:14:44,560
>> STUDENT: The location.

1496
01:14:44,560 --> 01:14:45,270
>> JASON HIRSHHORN: Exactly.

1497
01:14:45,270 --> 01:14:46,925
So give me that line in code.

1498
01:14:46,925 --> 01:14:53,310
>> STUDENT: smallest_location = j.

1499
01:14:53,310 --> 01:14:54,790
>> JASON HIRSHHORN: Exactly.

1500
01:14:54,790 --> 01:14:58,210
And then down at the end, if we want to
put the beginning of the list where

1501
01:14:58,210 --> 01:15:00,790
the smallest number was, how
do we refer to where the

1502
01:15:00,790 --> 01:15:02,200
smallest number was?

1503
01:15:02,200 --> 01:15:03,580
Marcus?

1504
01:15:03,580 --> 01:15:08,530
>> STUDENT: The smallest number was
located at smallest location.

1505
01:15:08,530 --> 01:15:12,230
>> JASON HIRSHHORN: So at values
smallest_location.

1506
01:15:12,230 --> 01:15:14,700
And what do we put there?

1507
01:15:14,700 --> 01:15:17,600
The beginning of the
list, what's that?

1508
01:15:17,600 --> 01:15:19,710
>> STUDENT: Well, we don't really know
anymore because we overwrote.

1509
01:15:19,710 --> 01:15:23,250
So it's a swapped locations
of those two lines?

1510
01:15:23,250 --> 01:15:26,110
If you switch those two lines around.

1511
01:15:26,110 --> 01:15:30,740
>> JASON HIRSHHORN: OK, so we don't
anymore, because we've reset the line

1512
01:15:30,740 --> 01:15:31,960
before values i to smallest.

1513
01:15:31,960 --> 01:15:33,810
So we lost that initial value.

1514
01:15:33,810 --> 01:15:37,350
So you said swap these two lines.

1515
01:15:37,350 --> 01:15:41,780
So now put the beginning of the list
where the smallest number was.

1516
01:15:41,780 --> 01:15:47,060
So smallest_location equals values i.

1517
01:15:47,060 --> 01:15:51,310
That's moving the beginning of this
unsorted portion of the list to the

1518
01:15:51,310 --> 01:15:52,090
smallest location.

1519
01:15:52,090 --> 01:15:54,860
And then into values i we're moving
that smallest number.

1520
01:15:54,860 --> 01:15:57,450
>> Does that make sense why we
had to make that swap?

1521
01:15:57,450 --> 01:15:59,650
We would have overwritten that value--
another thing you probably would have

1522
01:15:59,650 --> 01:16:02,740
figured out and found in GDP.

1523
01:16:02,740 --> 01:16:05,310
So we've taken care of
all the pseudocode.

1524
01:16:05,310 --> 01:16:10,935
Is there anything else we
need to write here?

1525
01:16:10,935 --> 01:16:14,911
Can anybody think of anything?

1526
01:16:14,911 --> 01:16:16,180
>> STUDENT: How do you know
when you're done?

1527
01:16:16,180 --> 01:16:17,680
>> JASON HIRSHHORN: How do we
know when we're done?

1528
01:16:17,680 --> 01:16:18,890
Great question.

1529
01:16:18,890 --> 01:16:21,684
So how do we know when we're done.

1530
01:16:21,684 --> 01:16:24,720
>> STUDENT: Create a variable to keep count
of if there's a swap made or not

1531
01:16:24,720 --> 01:16:27,810
and go through a pass.

1532
01:16:27,810 --> 01:16:30,180
>> JASON HIRSHHORN: OK.

1533
01:16:30,180 --> 01:16:31,800
That would work in bubble sort.

1534
01:16:31,800 --> 01:16:35,210
But for selection sort, if we don't
make a swap, that might just be

1535
01:16:35,210 --> 01:16:38,670
because the smallest value is
in it its right location.

1536
01:16:38,670 --> 01:16:41,240
We might have a list 1, 2, 4, 3.

1537
01:16:41,240 --> 01:16:42,830
The second time through we
won't make any swaps.

1538
01:16:42,830 --> 01:16:47,260
We'll be on the number 2, but we'll
still need to keep going.

1539
01:16:47,260 --> 01:16:49,390
So do we need to keep track of when
we're done, or do we just want to go

1540
01:16:49,390 --> 01:16:50,640
until this is finished?

1541
01:16:50,640 --> 01:16:54,098

1542
01:16:54,098 --> 01:16:56,740
>> STUDENT: We can just go
until it's finished.

1543
01:16:56,740 --> 01:16:58,090
>> JASON HIRSHHORN: We can just
go until this is finished.

1544
01:16:58,090 --> 01:17:01,720
In bubble sort, you're exactly right,
Jeff and Aleha, with your solution--

1545
01:17:01,720 --> 01:17:04,990
it is great to keep track of how many
swaps you made, because in bubble

1546
01:17:04,990 --> 01:17:07,920
sort, if you do in fact make no swaps,
you're done and you can maybe cut your

1547
01:17:07,920 --> 01:17:09,000
problem down a bit.

1548
01:17:09,000 --> 01:17:11,440
But for selection sort, you've really
got to go through to the end of the

1549
01:17:11,440 --> 01:17:14,940
list each time around.

1550
01:17:14,940 --> 01:17:16,200
>> So this is that.

1551
01:17:16,200 --> 01:17:18,530
We have two minutes left.

1552
01:17:18,530 --> 01:17:21,560
Let's make all.

1553
01:17:21,560 --> 01:17:24,340
Let me just open Find here and make
sure I'm in fact calling up--

1554
01:17:24,340 --> 01:17:25,610
I'm not calling bubble sort.

1555
01:17:25,610 --> 01:17:29,230
Let's change this to selection sort.

1556
01:17:29,230 --> 01:17:31,060
make all ./ find.

1557
01:17:31,060 --> 01:17:32,360
Let's find 42.

1558
01:17:32,360 --> 01:17:38,110
This time we're going to pass an
unsorted list, because it should sort

1559
01:17:38,110 --> 01:17:43,790
first, per the find code-- should sort
first using our sort function and then

1560
01:17:43,790 --> 01:17:44,995
look for something.

1561
01:17:44,995 --> 01:17:46,245
Fingers crossed everyone.

1562
01:17:46,245 --> 01:17:48,530

1563
01:17:48,530 --> 01:17:49,370
>> Oh my goodness.

1564
01:17:49,370 --> 01:17:50,800
Whoa, my heart was beating.

1565
01:17:50,800 --> 01:17:52,320
So that is correct.

1566
01:17:52,320 --> 01:17:57,270
In fact, if we ran this more
extensively, the code, as far as I can

1567
01:17:57,270 --> 01:17:59,280
tell, is perfectly correct.

1568
01:17:59,280 --> 01:18:02,150
There are some suggestions
I would have for you.

1569
01:18:02,150 --> 01:18:06,215
For example, 15 and 16 seem
a little redundant.

1570
01:18:06,215 --> 01:18:09,450
It seems like you don't necessarily
need to save both those.

1571
01:18:09,450 --> 01:18:12,790
If you have the smallest location, you
can easily find the smallest value by

1572
01:18:12,790 --> 01:18:14,750
just typing values of i.

1573
01:18:14,750 --> 01:18:18,100
>> So if I were to be grading your code,
which I will in fact be, I would

1574
01:18:18,100 --> 01:18:21,160
probably take off a point if you
included both of these, because you

1575
01:18:21,160 --> 01:18:22,670
don't need both of these.

1576
01:18:22,670 --> 01:18:25,400
If you have the location, you can
very easily get the value.

1577
01:18:25,400 --> 01:18:27,520
And it seems a little weird
to store both of them.

1578
01:18:27,520 --> 01:18:31,070
Maybe not even take a point, but
certainly comment that that is maybe

1579
01:18:31,070 --> 01:18:32,670
not a stylistic choice
you need to make.

1580
01:18:32,670 --> 01:18:35,290
Of course, the code still
runs perfectly well.

1581
01:18:35,290 --> 01:18:36,860
>> So unfortunately we didn't
get to bubble sort.

1582
01:18:36,860 --> 01:18:37,940
I'm sorry about that.

1583
01:18:37,940 --> 01:18:39,135
We did finish selection sort.

1584
01:18:39,135 --> 01:18:41,450
Does anybody have any final questions
about selection sort?

1585
01:18:41,450 --> 01:18:44,320

1586
01:18:44,320 --> 01:18:47,690
>> OK, before we head out, I want you
to open up your Chrome browser.

1587
01:18:47,690 --> 01:18:54,340
Sorry, that was just a blatant plug
for one type of internet browser.

1588
01:18:54,340 --> 01:18:57,770
You can open up any type of browser,
but it'll probably be Chrome.

1589
01:18:57,770 --> 01:19:01,250
And go to this following website--

1590
01:19:01,250 --> 01:19:06,410
sayat.me/cs50.

1591
01:19:06,410 --> 01:19:07,685
If you're not typing in your computer
right now, you're clearly

1592
01:19:07,685 --> 01:19:10,210
not doing it, Tom.

1593
01:19:10,210 --> 01:19:12,870
>> And please do it either right
now or in the next hour--

1594
01:19:12,870 --> 01:19:14,260
give me some feedback.

1595
01:19:14,260 --> 01:19:15,660
This is only section two.

1596
01:19:15,660 --> 01:19:18,060
We have many more together, so I
have a lot of room to improve.

1597
01:19:18,060 --> 01:19:19,620
I hopefully also did some things well.

1598
01:19:19,620 --> 01:19:22,160
So you can make me feel all bad, but if
you also want to give me a smiley

1599
01:19:22,160 --> 01:19:24,250
face, I would appreciate that as well.

1600
01:19:24,250 --> 01:19:25,330
Fill that in.

1601
01:19:25,330 --> 01:19:28,210
>> And with one minute left,
that was week three.

1602
01:19:28,210 --> 01:19:30,750
I'll stand outside for a bit
if you have any questions.

1603
01:19:30,750 --> 01:19:32,220
I will see you guys in
lecture tomorrow.

1604
01:19:32,220 --> 01:19:34,742