1
00:00:00,000 --> 00:00:03,000
[Section 3] [Less Comfortable]

2
00:00:03,000 --> 00:00:05,000
>> [Nate Hardison] [Harvard University]

3
00:00:05,000 --> 00:00:08,000
>> [This is CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:10,000
>> All right, let's get started.

5
00:00:10,000 --> 00:00:13,000
Welcome to Week 4 of CS50.

6
00:00:13,000 --> 00:00:19,000
If you guys open up a web browser and open up pset 3,

7
00:00:19,000 --> 00:00:23,000
Scramble with CS50, we're going to start going

8
00:00:23,000 --> 00:00:26,000
through the section of questions there.

9
00:00:26,000 --> 00:00:32,000
Just like last week, we'll be working in CS50 Spaces,

10
00:00:32,000 --> 00:00:35,000
if you'll also pull that up as well,

11
00:00:35,000 --> 00:00:43,000
and if you go ahead and visit this link that I've got up here at the top.

12
00:00:43,000 --> 00:00:45,000
It's time to get started.

13
00:00:45,000 --> 00:00:51,000
We've got our little hi program here. Nothing crazy.

14
00:00:51,000 --> 00:00:55,000
One of the first things I want to do with you guys today is go over a few solutions

15
00:00:55,000 --> 00:00:58,000
to Problem Set 1, kind of example solutions,

16
00:00:58,000 --> 00:01:03,000
just so you can get a feel for what kinds of code staff is writing,

17
00:01:03,000 --> 00:01:07,000
what kinds of code other students are writing,

18
00:01:07,000 --> 00:01:10,000
and have you take a look at it because I know it's weird

19
00:01:10,000 --> 00:01:14,000
when you submit a solution to a problem set and get comments

20
00:01:14,000 --> 00:01:18,000
on your own version, but sometimes it's helpful to see how other people did it,

21
00:01:18,000 --> 00:01:22,000
especially ones that are nice looking.

22
00:01:22,000 --> 00:01:27,000
For the most part, I was really impressed with the solutions that you guys produced.

23
00:01:27,000 --> 00:01:31,000
I haven't yet started looking at your Problem Set 2s, but if they're anything like the first,

24
00:01:31,000 --> 00:01:34,000
it means nothing but good things.

25
00:01:34,000 --> 00:01:40,000
>> If you look at my revisions, let's start all the way down at Revision 1,

26
00:01:40,000 --> 00:01:47,000
and we're going to take a quick look at a Mario solution.

27
00:01:47,000 --> 00:01:54,000
If you pull this up, these programs that we're going to present are correct.

28
00:01:54,000 --> 00:01:56,000
There weren't correctness issues with these problems, but rather,

29
00:01:56,000 --> 00:01:59,000
we want to talk a little bit about the different design issues

30
00:01:59,000 --> 00:02:03,000
that were being used here.

31
00:02:03,000 --> 00:02:08,000
One of the things that was interesting about the solution

32
00:02:08,000 --> 00:02:11,000
is that it used this new construct called pound define,

33
00:02:11,000 --> 00:02:15,000
sometimes also referred to as a hash define.

34
00:02:15,000 --> 00:02:18,000
Let me zoom in on it here.

35
00:02:18,000 --> 00:02:24,000
A #define allows you to give names to these numbers in your program.

36
00:02:24,000 --> 00:02:28,000
In this case, the maximum height of a pyramid in Mario

37
00:02:28,000 --> 00:02:34,000
was 23 and rather than putting 23 in my code—

38
00:02:34,000 --> 00:02:37,000
we would refer to that as hard coding 23—

39
00:02:37,000 --> 00:02:43,000
instead this gives the name MAX_HEIGHT to that number,

40
00:02:43,000 --> 00:02:48,000
so that down here in my do-while loop

41
00:02:48,000 --> 00:02:51,000
you can actually refer to MAX_HEIGHT

42
00:02:51,000 --> 00:02:55,000
instead of putting the number 23 in.

43
00:02:55,000 --> 00:02:57,000
[Student] What is the advantage of doing that?

44
00:02:57,000 --> 00:02:59,000
That's a great question.

45
00:02:59,000 --> 00:03:03,000
One is readability.

46
00:03:03,000 --> 00:03:08,000
An advantage of using this #define is readability.

47
00:03:08,000 --> 00:03:11,000
When I'm reading this code, I can see what's going on.

48
00:03:11,000 --> 00:03:15,000
>> I can see in this condition here that we're testing

49
00:03:15,000 --> 00:03:19,000
for the height being < 0, which we could have also defined

50
00:03:19,000 --> 00:03:22,000
to be a minimum height or a min height.

51
00:03:22,000 --> 00:03:25,000
The other advantage is that I can then read the rest of the line to see

52
00:03:25,000 --> 00:03:30,000
that we're also checking to make sure that height is not greater than the max height,

53
00:03:30,000 --> 00:03:35,000
because we're going to continue while the height is greater than the max height.

54
00:03:35,000 --> 00:03:40,000
The other advantage is—if I zoom out a little bit here—

55
00:03:40,000 --> 00:03:49,000
if I run this program and I run it, say, with 23 right now,

56
00:03:49,000 --> 00:03:52,000
it will print out all 23 rows just like that.

57
00:03:52,000 --> 00:03:54,000
But say I wanted to change the max height,

58
00:03:54,000 --> 00:03:57,000
and now I want to limit the maximum height of pyramids

59
00:03:57,000 --> 00:04:06,000
to be only say—man, that was funky.

60
00:04:06,000 --> 00:04:14,000
#include <stdio.h>, #define MAX_HEIGHT,

61
00:04:14,000 --> 00:04:18,000
and let's say we wanted to set it equal to 10.

62
00:04:18,000 --> 00:04:22,000
Now at this point, all I had to do was change it in this one location.

63
00:04:22,000 --> 00:04:27,000
I can recompile the code, and now if I try and type in 12,

64
00:04:27,000 --> 00:04:30,000
it will prompt me again.

65
00:04:30,000 --> 00:04:33,000
In this case, we're only using MAX_HEIGHT once.

66
00:04:33,000 --> 00:04:37,000
It's not that big of a hassle to go in

67
00:04:37,000 --> 00:04:40,000
and change it in the while loop if you need to.

68
00:04:40,000 --> 00:04:44,000
But in programs where you're referencing the same magic number

69
00:04:44,000 --> 00:04:47,000
over and over again, this #define mechanism is really handy

70
00:04:47,000 --> 00:04:52,000
because you just change it one time at the top of the file—it's typically where you put them—

71
00:04:52,000 --> 00:04:57,000
and the change percolates through the rest of the file.

72
00:04:57,000 --> 00:05:02,000
>> Other things I wanted to note in this assignment that I thought looked really nice,

73
00:05:02,000 --> 00:05:05,000
one was the naming of the variables.

74
00:05:05,000 --> 00:05:14,000
You see here that we've got integer variables called row and called height.

75
00:05:14,000 --> 00:05:20,000
Spaces, hashes, it helps make the code a little more readable,

76
00:05:20,000 --> 00:05:25,000
makes it a little more understandable what's actually going on.

77
00:05:25,000 --> 00:05:31,000
This is in contrast to using, say, random letters

78
00:05:31,000 --> 00:05:35,000
or just gobbledygook altogether.

79
00:05:35,000 --> 00:05:39,000
A final thing I'll point out is that in for loops,

80
00:05:39,000 --> 00:05:45,000
often these iterator variables, these counters that you use in your for loops,

81
00:05:45,000 --> 00:05:51,000
it's standard and conventional to start them with either i and then j and then k

82
00:05:51,000 --> 00:05:54,000
and going on from there if you need more variables,

83
00:05:54,000 --> 00:05:56,000
and this is just a convention.

84
00:05:56,000 --> 00:05:58,000
There are lots of conventions.

85
00:05:58,000 --> 00:06:00,000
It depends on the programming language you're using.

86
00:06:00,000 --> 00:06:04,000
But in C, we typically start with i.

87
00:06:04,000 --> 00:06:08,000
It doesn't make sense to use, say, a or b

88
00:06:08,000 --> 00:06:13,000
depending on the situation.

89
00:06:13,000 --> 00:06:15,000
That's it for this one.

90
00:06:15,000 --> 00:06:25,000
If you now pull up Revision 2, you'll see another Mario,

91
00:06:25,000 --> 00:06:29,000
and this one is similar to the other one that we just saw,

92
00:06:29,000 --> 00:06:32,000
but it does something kind of cool.

93
00:06:32,000 --> 00:06:38,000
If we look at this section right here inside the inner for loop,

94
00:06:38,000 --> 00:06:44,000
they're using some crazy looking syntax here right in this line.

95
00:06:44,000 --> 00:06:47,000
This is called a ternary operator.

96
00:06:47,000 --> 00:06:53,000
It is an if else statement condensed into one line.

97
00:06:53,000 --> 00:06:57,000
The condition is this part within parentheses.

98
00:06:57,000 --> 00:07:05,000
It's equivalent to saying if j < height - i - 1.

99
00:07:05,000 --> 00:07:10,000
And then what the contents of that if block would be are the space

100
00:07:10,000 --> 00:07:16,000
and then the contents of what the else would be are this #.

101
00:07:16,000 --> 00:07:20,000
It's essentially assigning a space to this variable.

102
00:07:20,000 --> 00:07:24,000
It's putting a space in the contents of the block variable,

103
00:07:24,000 --> 00:07:29,000
if this condition is met, and if the condition is not met,

104
00:07:29,000 --> 00:07:32,000
then the block variable gets this #.

105
00:07:32,000 --> 00:07:37,000
And then, of course, instead of building up an entire string

106
00:07:37,000 --> 00:07:43,000
and printing everything out at the end this solution prints it out one character at a time.

107
00:07:43,000 --> 00:07:48,000
Pretty cool.

108
00:07:48,000 --> 00:07:53,000
>> Another couple of things to look at. We'll move on to greedy.

109
00:07:53,000 --> 00:07:58,000
Now if we look at greedy, this first solution

110
00:07:58,000 --> 00:08:00,000
uses these #defines quite a bit.

111
00:08:00,000 --> 00:08:06,000
We've got one constant defined for each of the different numbers in this program.

112
00:08:06,000 --> 00:08:12,000
We've got one for cents per dollar, one for quarters, dimes, nickels, and pennies,

113
00:08:12,000 --> 00:08:15,000
and now if we scroll down and read the code,

114
00:08:15,000 --> 00:08:22,000
we can see a standard do-while loop printing everything out.

115
00:08:22,000 --> 00:08:25,000
Kind of the crux of this problem was realizing that

116
00:08:25,000 --> 00:08:29,000
you needed to convert the float that you read in from the user to an integer

117
00:08:29,000 --> 00:08:32,000
to accurately do the math, and this is because

118
00:08:32,000 --> 00:08:36,000
with floating point numbers, like we talked about in lecture briefly,

119
00:08:36,000 --> 00:08:41,000
it's not possible to accurately represent every single value on the number line

120
00:08:41,000 --> 00:08:47,000
because there are infinitely many values between 3 and, say, 3.1 even.

121
00:08:47,000 --> 00:08:54,000
You can have 3.01 and 3.001 and 3.0001, and you can keep going.

122
00:08:54,000 --> 00:09:00,000
It turns out whenever you're working with money, you often want to convert it

123
00:09:00,000 --> 00:09:05,000
into integer format so that you're not losing pennies and that kind of stuff.

124
00:09:05,000 --> 00:09:09,000
Doing that and rounding was key.

125
00:09:09,000 --> 00:09:14,000
This solution used a perfectly straightforward, great algorithm,

126
00:09:14,000 --> 00:09:17,000
which decremented the number of cents remaining, first by quarters,

127
00:09:17,000 --> 00:09:19,000
then by dimes, then by nickels, then by pennies,

128
00:09:19,000 --> 00:09:24,000
and adding to the number of coins each time.

129
00:09:24,000 --> 00:09:31,000
>> Another solution that we'll see, as I zoom out and go to Revision 4,

130
00:09:31,000 --> 00:09:40,000
had a very similar beginning but instead used div and mod

131
00:09:40,000 --> 00:09:44,000
right over here to calculate the number of cents.

132
00:09:44,000 --> 00:09:50,000
This, the number of quarters is equal to the number of cents divided by 25,

133
00:09:50,000 --> 00:09:53,000
and the reason this works is because we're doing integer division,

134
00:09:53,000 --> 00:09:58,000
so it's discarding any remainder.

135
00:09:58,000 --> 00:10:02,000
[Student] Do we have to comment the search?

136
00:10:02,000 --> 00:10:05,000
It really depends.

137
00:10:05,000 --> 00:10:08,000
[Student] You're commenting more than code right here.

138
00:10:08,000 --> 00:10:16,000
Yeah, and so there are a bunch of varying philosophies on this.

139
00:10:16,000 --> 00:10:21,000
My personal philosophy is that your code is really the truth,

140
00:10:21,000 --> 00:10:24,000
like your code is what's actually executing on the computer,

141
00:10:24,000 --> 00:10:29,000
and so your code should be as readable as possible to not necessitate as many comments.

142
00:10:29,000 --> 00:10:33,000
That said, when you are doing things that are kind of tricky mathematically

143
00:10:33,000 --> 00:10:38,000
or algorithmically, it's good to comment those so that you can

144
00:10:38,000 --> 00:10:43,000
add an extra dimension, an extra layer to whoever is reading your code.

145
00:10:43,000 --> 00:10:49,000
In these solutions, often they are commented more heavily just because

146
00:10:49,000 --> 00:10:52,000
we want to be able to distribute them and have people pick them up

147
00:10:52,000 --> 00:10:56,000
and read them pretty easily.

148
00:10:56,000 --> 00:11:05,000
But definitely, I would agree that this is heavy.

149
00:11:05,000 --> 00:11:07,000
[Student] But when in doubt, go heavier?

150
00:11:07,000 --> 00:11:10,000
When in doubt, go heavier.

151
00:11:10,000 --> 00:11:17,000
Some people will sometimes say return 0 or something like that.

152
00:11:17,000 --> 00:11:20,000
I think that's a ridiculous comment.

153
00:11:20,000 --> 00:11:22,000
Clearly that's what's happening.

154
00:11:22,000 --> 00:11:25,000
I don't need English to tell me that.

155
00:11:25,000 --> 00:11:28,000
Sometimes people will write stuff like "kthxbai!"

156
00:11:28,000 --> 00:11:32,000
That's kind of cute but also not—

157
00:11:32,000 --> 00:11:35,000
that's not making the difference between commenting points or not.

158
00:11:35,000 --> 00:11:41,000
Those kinds of comments are just ha, ha.

159
00:11:41,000 --> 00:11:43,000
Cool.

160
00:11:43,000 --> 00:11:48,000
>> At this point, let's start working on the Problem Set 3 section of questions.

161
00:11:48,000 --> 00:11:52,000
If you guys pull this up again,

162
00:11:52,000 --> 00:11:55,000
as with last week, we're not going to watch the shorts in this section.

163
00:11:55,000 --> 00:12:00,000
We'll let you guys do that on your own time and talk about the questions.

164
00:12:00,000 --> 00:12:05,000
But now in this section we're going to spend a little more time

165
00:12:05,000 --> 00:12:11,000
talking about less of the coding basics

166
00:12:11,000 --> 00:12:15,000
like we did last week, and instead, we're going to focus more on

167
00:12:15,000 --> 00:12:22,000
a little bit more of the theory, so talking about binary search and then sorting.

168
00:12:22,000 --> 00:12:27,000
From those of you who have been following along with the lecture,

169
00:12:27,000 --> 00:12:30,000
can somebody give me a recap of what the difference is

170
00:12:30,000 --> 00:12:35,000
between binary search and linear search?

171
00:12:35,000 --> 00:12:37,000
What's going on? Sure.

172
00:12:37,000 --> 00:12:42,000
Linear search searches through every element in the sorted list

173
00:12:42,000 --> 00:12:45,000
one by one by one by one by one,

174
00:12:45,000 --> 00:12:50,000
and binary search divides the list into 2 groups,

175
00:12:50,000 --> 00:12:57,000
checks if the keys value that you're searching for is greater than or less than the midpoint value

176
00:12:57,000 --> 00:13:00,000
that you just found, and if it's less than, it goes with the lower list

177
00:13:00,000 --> 00:13:03,000
and then divides that again, does the same function

178
00:13:03,000 --> 00:13:07,000
all the way down until it finds the midpoint to be equal to the value itself.

179
00:13:07,000 --> 00:13:10,000
Right.

180
00:13:10,000 --> 00:13:12,000
>> Why do we care?

181
00:13:12,000 --> 00:13:20,000
Why do we talk about binary search versus linear search?

182
00:13:20,000 --> 00:13:22,000
Yeah.

183
00:13:22,000 --> 00:13:24,000
Binary is a lot faster, so if you double the size of the problem

184
00:13:24,000 --> 00:13:27,000
it takes one more step rather than twice as many.

185
00:13:27,000 --> 00:13:29,000
Exactly.

186
00:13:29,000 --> 00:13:31,000
That's a great answer.

187
00:13:31,000 --> 00:13:36,000
Linear search is very much checking one element at a time,

188
00:13:36,000 --> 00:13:39,000
and as we saw on the very first day of lecture

189
00:13:39,000 --> 00:13:42,000
when David went through his phone book example

190
00:13:42,000 --> 00:13:45,000
and ripped out one page of the phone book at a time

191
00:13:45,000 --> 00:13:47,000
and kept doing that over and over and over again,

192
00:13:47,000 --> 00:13:51,000
it's going to take him a really long time to find anybody in the phone book,

193
00:13:51,000 --> 00:13:55,000
unless, of course, he was looking for somebody at the very beginning of the alphabet.

194
00:13:55,000 --> 00:14:00,000
With binary search, you can go a lot faster,

195
00:14:00,000 --> 00:14:05,000
and it's not just twice as fast or 3 times as fast or 4 times as fast.

196
00:14:05,000 --> 00:14:13,000
But the problem gets smaller and smaller and smaller much faster.

197
00:14:13,000 --> 00:14:17,000
To illustrate this, we'll start talking about what's going on

198
00:14:17,000 --> 00:14:21,000
when we write binary search.

199
00:14:21,000 --> 00:14:27,000
The problem at hand is that if I have an array of numbers,

200
00:14:27,000 --> 00:14:40,000
say, 1, 2, 3, 5, 7, 23, 45, 78, 12323,

201
00:14:40,000 --> 00:14:47,000
and then 9 with a ton of 0s after it,

202
00:14:47,000 --> 00:14:52,000
we want to be able to figure out really quickly what is in

203
00:14:52,000 --> 00:14:57,000
this array of numbers.

204
00:14:57,000 --> 00:15:00,000
I know this seems a little silly and a little contrived,

205
00:15:00,000 --> 00:15:02,000
because right now it is.

206
00:15:02,000 --> 00:15:05,000
We have an array that doesn't have very many elements in it,

207
00:15:05,000 --> 00:15:08,000
and if I ask one of you to figure out whether or not

208
00:15:08,000 --> 00:15:11,000
23 is in the array, you can do that pretty quickly

209
00:15:11,000 --> 00:15:16,000
just by glancing at this and telling me yes or no.

210
00:15:16,000 --> 00:15:20,000
The analog to consider is imagine if this were, say,

211
00:15:20,000 --> 00:15:27,000
an Excel spreadsheet with 10,000 rows, 20,000 rows.

212
00:15:27,000 --> 00:15:31,000
Of course, you can do the command F or the control F and look something up.

213
00:15:31,000 --> 00:15:33,000
You can also use the filters and the search stuff,

214
00:15:33,000 --> 00:15:37,000
but if you had to look through that file line by line by line,

215
00:15:37,000 --> 00:15:40,000
it would take you a long time to find it.

216
00:15:40,000 --> 00:15:42,000
It's kind of like in the phone book example, too, where

217
00:15:42,000 --> 00:15:44,000
nobody looks through a phone book one page at a time.

218
00:15:44,000 --> 00:15:47,000
Typically, they do open it to the middle,

219
00:15:47,000 --> 00:15:50,000
or in the case of a lot of phone books and dictionaries where

220
00:15:50,000 --> 00:15:54,000
you actually have it keyed on the first letter,

221
00:15:54,000 --> 00:16:01,000
you flip to that first letter and open and start going through there.

222
00:16:01,000 --> 00:16:03,000
>> Remind me of your name again.>>Sam.

223
00:16:03,000 --> 00:16:05,000
Sam.

224
00:16:05,000 --> 00:16:11,000
Like Sam said, that linear search process is going to be really slow,

225
00:16:11,000 --> 00:16:15,000
and instead with binary search, the way this works is that

226
00:16:15,000 --> 00:16:21,000
every time we go through an iteration of our searching algorithm,

227
00:16:21,000 --> 00:16:27,000
we're going to divide the list in half, essentially,

228
00:16:27,000 --> 00:16:33,000
into two smaller lists.

229
00:16:33,000 --> 00:16:39,000
And then on the next iteration of the loop, we'll divide it again

230
00:16:39,000 --> 00:16:44,000
into other smaller lists.

231
00:16:44,000 --> 00:16:48,000
As you can see, the problem keeps getting smaller and smaller

232
00:16:48,000 --> 00:16:55,000
because we keep discarding half of the list every single time.

233
00:16:55,000 --> 00:16:59,000
How does this discard work?

234
00:16:59,000 --> 00:17:05,000
Just as a reminder, what we're going to do if we were a computer

235
00:17:05,000 --> 00:17:11,000
and we were, say, searching for the number 5 in this list

236
00:17:11,000 --> 00:17:15,000
is that we would pick a number in the middle.

237
00:17:15,000 --> 00:17:26,000
In the middle of this list, because there are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 numbers,

238
00:17:26,000 --> 00:17:32,000
we'd pick the number either at the 4th position or at the 5th position,

239
00:17:32,000 --> 00:17:38,000
and we'd call that the middle of our list.

240
00:17:38,000 --> 00:17:42,000
Pick number in middle.

241
00:17:42,000 --> 00:17:51,000
Then, just like Sam said, we'll test to see if that number is equal

242
00:17:51,000 --> 00:17:59,000
to the number that we want to get or our desired number.

243
00:17:59,000 --> 00:18:06,000
If it's equal, then we've found it. We win.

244
00:18:06,000 --> 00:18:12,000
If it's not equal, then there are a couple of cases.

245
00:18:12,000 --> 00:18:15,000
The two cases are either the number has to be greater than the number we're looking at,

246
00:18:15,000 --> 00:18:19,000
or it's less than.

247
00:18:19,000 --> 00:18:25,000
If it's greater, we move to the right.

248
00:18:25,000 --> 00:18:33,000
And if it's less, we move to the left.

249
00:18:33,000 --> 00:18:41,000
And then we repeat the whole process again

250
00:18:41,000 --> 00:18:48,000
on either the right half or the left half of the list.

251
00:18:48,000 --> 00:18:51,000
>> The first problem in today's section is to figure out

252
00:18:51,000 --> 00:18:55,000
how we can actually start to express this in C code.

253
00:18:55,000 --> 00:18:58,000
We've got the pseudocode here.

254
00:18:58,000 --> 00:19:04,000
What we'll start doing is I'll pull up a brand-new space,

255
00:19:04,000 --> 00:19:09,000
save this revision so that we have these notes for later,

256
00:19:09,000 --> 00:19:20,000
we'll delete all this, and then copy and paste from the problem set

257
00:19:20,000 --> 00:19:26,000
this information into our spaces, and hopefully this doesn't break.

258
00:19:26,000 --> 00:19:28,000
Perfect.

259
00:19:28,000 --> 00:19:33,000
If you guys all do that, copy and paste this code into your new space,

260
00:19:33,000 --> 00:19:43,000
into a blank one.

261
00:19:43,000 --> 00:19:47,000
Let's try Daniel. If you compile and run this program, does it work?

262
00:19:47,000 --> 00:19:49,000
No.>>What's it saying?

263
00:19:49,000 --> 00:19:53,000
It says the control reaches end of non-void function.

264
00:19:53,000 --> 00:19:55,000
Yeah, so let me try running it.

265
00:19:55,000 --> 00:19:59,000
Have you guys seen this before? Do you know what this means?

266
00:19:59,000 --> 00:20:01,000
Okay, let's dissect this a little bit.

267
00:20:01,000 --> 00:20:10,000
It's saying at file.c on line 9, column 1 we have an error, just like you said,

268
00:20:10,000 --> 00:20:16,000
and it says that it's stemming from the error warning and the return type warning.

269
00:20:16,000 --> 00:20:18,000
It looks like something is going on with the return type, which makes sense.

270
00:20:18,000 --> 00:20:21,000
We've got a non-void function, which means that we've got a function

271
00:20:21,000 --> 00:20:24,000
that doesn't return void.

272
00:20:24,000 --> 00:20:27,000
A void function is one that looks like this:

273
00:20:27,000 --> 00:20:35,000
void foo(), and it's void because the return type is void,

274
00:20:35,000 --> 00:20:38,000
which means that if we had something in here

275
00:20:38,000 --> 00:20:45,000
like return 1, we'd get a compiler error for this.

276
00:20:45,000 --> 00:20:49,000
However, we have a non-void function.

277
00:20:49,000 --> 00:20:51,000
Our non-void function in this case is our search function

278
00:20:51,000 --> 00:20:56,000
because it has a return type of bool.

279
00:20:56,000 --> 00:20:59,000
When it's saying that the control reaches the end of a non-void function,

280
00:20:59,000 --> 00:21:02,000
it's because search doesn't have a return statement.

281
00:21:02,000 --> 00:21:04,000
It's not returning anything of type bool.

282
00:21:04,000 --> 00:21:09,000
>> We can fix that, and what do you guys think

283
00:21:09,000 --> 00:21:13,000
search should return by default?

284
00:21:13,000 --> 00:21:16,000
What should be the default return value of search?

285
00:21:16,000 --> 00:21:19,000
Because that's what we can put at the end.

286
00:21:19,000 --> 00:21:21,000
Charlotte, do you have any—?

287
00:21:21,000 --> 00:21:23,000
True or false?>>True or false.

288
00:21:23,000 --> 00:21:26,000
Which one?

289
00:21:26,000 --> 00:21:28,000
False. I don't know.

290
00:21:28,000 --> 00:21:30,000
False? Let's try it.

291
00:21:30,000 --> 00:21:32,000
Why would you say return false? That's great intuition.

292
00:21:32,000 --> 00:21:35,000
[Charlotte] I don't know.

293
00:21:35,000 --> 00:21:39,000
We're going to return false in this case because this will be our default

294
00:21:39,000 --> 00:21:44,000
if for some reason the list is empty or the needle

295
00:21:44,000 --> 00:21:46,000
that we're looking for doesn't exist.

296
00:21:46,000 --> 00:21:50,000
Then at the very end, if we don't return true earlier in this function,

297
00:21:50,000 --> 00:21:55,000
we always know that this function will say nope, it's not in the array.

298
00:21:55,000 --> 00:21:58,000
It's not in the haystack.

299
00:21:58,000 --> 00:22:03,000
Now if we compile and run it—let me save this so we can pull it up.

300
00:22:03,000 --> 00:22:08,000
Now if we compile and run our program, it builds.

301
00:22:08,000 --> 00:22:12,000
We get our little prompt.

302
00:22:12,000 --> 00:22:20,000
If I hit 4—uh-oh.

303
00:22:20,000 --> 00:22:25,000
It didn't print out anything. It looks like everything ended okay.

304
00:22:25,000 --> 00:22:35,000
We've got to fill this in.

305
00:22:35,000 --> 00:22:39,000
We talked about the algorithm in pseudocode a little bit ago.

306
00:22:39,000 --> 00:22:44,000
Let me see, save this,

307
00:22:44,000 --> 00:22:49,000
and I'll pull that algorithm back up again.

308
00:22:49,000 --> 00:22:51,000
Let's hit this guy. Nope.

309
00:22:51,000 --> 00:22:58,000
There it is.

310
00:22:58,000 --> 00:23:03,000
How do we do this?

311
00:23:03,000 --> 00:23:11,000
What would be a good strategy for starting off this code?

312
00:23:11,000 --> 00:23:16,000
You have to pick a number in the middle.

313
00:23:16,000 --> 00:23:23,000
How do we pick a number in the middle of an array?

314
00:23:23,000 --> 00:23:25,000
Any suggestions?

315
00:23:25,000 --> 00:23:27,000
[Student] Strlen divided by 2.

316
00:23:27,000 --> 00:23:32,000
Strlen divided by 2. That's a great one.

317
00:23:32,000 --> 00:23:35,000
Strlen works with special kinds of arrays.

318
00:23:35,000 --> 00:23:38,000
What kinds of arrays?

319
00:23:38,000 --> 00:23:44,000
String arrays, character arrays.

320
00:23:44,000 --> 00:23:48,000
It's that same sort of concept that we want to apply,

321
00:23:48,000 --> 00:23:52,000
but we can't use strlen because we don't have an array of characters.

322
00:23:52,000 --> 00:23:55,000
We have an array of ints.

323
00:23:55,000 --> 00:23:58,000
But what does strlen get for us?

324
00:23:58,000 --> 00:24:01,000
Do you know what it gets for us?

325
00:24:01,000 --> 00:24:03,000
[Student] Strlen gets us the length.

326
00:24:03,000 --> 00:24:05,000
Exactly, it gets us the length.

327
00:24:05,000 --> 00:24:09,000
Strlen gets the length of the array for us.

328
00:24:09,000 --> 00:24:14,000
>> How do we get that in our binary search program?

329
00:24:14,000 --> 00:24:18,000
How would you get the length of an array?

330
00:24:18,000 --> 00:24:20,000
[Student] Strlen?

331
00:24:20,000 --> 00:24:25,000
You can get the length of a properly formatted C string array with strlen.

332
00:24:25,000 --> 00:24:31,000
The problem, though, is that we don't have a string array.

333
00:24:31,000 --> 00:24:36,000
If we look back at this code, we have this integer array.

334
00:24:36,000 --> 00:24:38,000
How do we know how long it is?

335
00:24:38,000 --> 00:24:44,000
[Student] Is there an equivalent one for endpoint, like int l or something?

336
00:24:44,000 --> 00:24:49,000
It turns out there actually isn't, and so in a way, this is

337
00:24:49,000 --> 00:24:52,000
one of those things that's just good to know about C,

338
00:24:52,000 --> 00:24:57,000
that there is no way to get the length of an array

339
00:24:57,000 --> 00:24:59,000
if all I give you is the array.

340
00:24:59,000 --> 00:25:02,000
The reason it works with strings, the reason strlen works,

341
00:25:02,000 --> 00:25:06,000
is because if a string is properly formatted,

342
00:25:06,000 --> 00:25:12,000
it will have that special \0 character at the very end.

343
00:25:12,000 --> 00:25:16,000
>> You can also imagine if you have an improperly formatted string

344
00:25:16,000 --> 00:25:20,000
and there's no \0 character there, then the whole thing doesn't work.

345
00:25:20,000 --> 00:25:22,000
[Student] Can you add the \0?

346
00:25:22,000 --> 00:25:24,000
We could in this case.

347
00:25:24,000 --> 00:25:29,000
We could add some sort of \0

348
00:25:29,000 --> 00:25:33,000
or some sort of signifying character and then use that.

349
00:25:33,000 --> 00:25:36,000
But that's not quite going to work

350
00:25:36,000 --> 00:25:40,000
because the \0 is for a char type,

351
00:25:40,000 --> 00:25:43,000
and here we've got ints.

352
00:25:43,000 --> 00:25:46,000
The other thing is if we were to use a special value

353
00:25:46,000 --> 00:25:49,000
like -1 to mark the end of an array

354
00:25:49,000 --> 00:25:54,000
then we could never store a -1 in our integer arrays.

355
00:25:54,000 --> 00:25:56,000
We'd be stuck.

356
00:25:56,000 --> 00:26:00,000
It turns out that the only way to get the length

357
00:26:00,000 --> 00:26:03,000
of an array in C is to actually remember it

358
00:26:03,000 --> 00:26:08,000
when you set it up and then pass it around with the array

359
00:26:08,000 --> 00:26:14,000
so that whenever I have a function that's going to do some work

360
00:26:14,000 --> 00:26:18,000
on an array of integers or floats or doubles or what have you,

361
00:26:18,000 --> 00:26:22,000
I also need to give the function the array's length,

362
00:26:22,000 --> 00:26:26,000
and that's exactly what we've done here in the search function.

363
00:26:26,000 --> 00:26:30,000
If you look, what we've done when we pass in our array here,

364
00:26:30,000 --> 00:26:36,000
we also pass in the length, the size.

365
00:26:36,000 --> 00:26:41,000
It just happens that we have called this variable here,

366
00:26:41,000 --> 00:26:43,000
this parameter or argument.

367
00:26:43,000 --> 00:26:46,000
This is called a function's argument list or parameter list,

368
00:26:46,000 --> 00:26:51,000
and these are also called arguments or parameters.

369
00:26:51,000 --> 00:26:53,000
People use different terms at different times.

370
00:26:53,000 --> 00:26:55,000
I sometimes interchange them myself.

371
00:26:55,000 --> 00:27:00,000
It just so happens that this variable here is named similarly

372
00:27:00,000 --> 00:27:03,000
to this #define up here.

373
00:27:03,000 --> 00:27:06,000
But they're not the same thing.

374
00:27:06,000 --> 00:27:11,000
The capitalization does matter.

375
00:27:11,000 --> 00:27:14,000
>> If you look at what happens here, we declare

376
00:27:14,000 --> 00:27:18,000
our int array, which we've called numbers.

377
00:27:18,000 --> 00:27:23,000
We've given it our size, which corresponds to our #define up at the top.

378
00:27:23,000 --> 00:27:27,000
It's going to be 8.

379
00:27:27,000 --> 00:27:35,000
And then when we then call our search function down below,

380
00:27:35,000 --> 00:27:40,000
we pass in the number we want to search for, which we've prompted,

381
00:27:40,000 --> 00:27:43,000
gotten from the user.

382
00:27:43,000 --> 00:27:46,000
We pass in the array, this numbers,

383
00:27:46,000 --> 00:27:51,000
and then we also have to pass in the size of the array,

384
00:27:51,000 --> 00:27:57,000
and then the value of size 8 gets stored

385
00:27:57,000 --> 00:28:01,000
or passed to this integer variable called size.

386
00:28:01,000 --> 00:28:08,000
We have the size of the array.

387
00:28:08,000 --> 00:28:11,000
Now if we go back to what we were talking about earlier,

388
00:28:11,000 --> 00:28:14,000
I think Missy brought up the point that what we needed to do is get the length of the array

389
00:28:14,000 --> 00:28:20,000
and divide it by 2, and that will give us the midpoint.

390
00:28:20,000 --> 00:28:22,000
Let's see.

391
00:28:22,000 --> 00:28:25,000
Can I have somebody write this and save it in their space?

392
00:28:25,000 --> 00:28:27,000
How about Leila?

393
00:28:27,000 --> 00:28:31,000
Can I have you write this in?

394
00:28:31,000 --> 00:28:35,000
Write the first line where you take the length of the array and get the midpoint

395
00:28:35,000 --> 00:28:41,000
and store it in a new variable.

396
00:28:41,000 --> 00:28:44,000
I'll give you a couple seconds. Are you ready?

397
00:28:44,000 --> 00:28:46,000
[Student inaudible]

398
00:28:46,000 --> 00:28:50,000
Sure, could I have you calculate the midpoint

399
00:28:50,000 --> 00:28:55,000
of the haystack array inside the search function

400
00:28:55,000 --> 00:29:03,000
using the length of the haystack array, which is the size variable?

401
00:29:03,000 --> 00:29:08,000
Nothing tricky here.

402
00:29:08,000 --> 00:29:12,000
[Leila] Just size/2 and just—

403
00:29:12,000 --> 00:29:17,000
And save it, and hit the Save button up here at the top,

404
00:29:17,000 --> 00:29:19,000
and we'll pull it up.

405
00:29:19,000 --> 00:29:22,000
Perfect.

406
00:29:22,000 --> 00:29:28,000
There we go. Awesome.

407
00:29:28,000 --> 00:29:30,000
>> As is, will this compile?

408
00:29:30,000 --> 00:29:32,000
[Leila] No, it needs to be higher.

409
00:29:32,000 --> 00:29:34,000
[Nate] Yeah, so what do we need to do?

410
00:29:34,000 --> 00:29:36,000
[Leila] Like int midpoint or something.

411
00:29:36,000 --> 00:29:41,000
Awesome. Yeah, let's do that, int midpoint = size.

412
00:29:41,000 --> 00:29:44,000
Will this compile?

413
00:29:44,000 --> 00:29:47,000
Let's delete this comment and get it out of the way.

414
00:29:47,000 --> 00:29:50,000
What won't compile about this?

415
00:29:50,000 --> 00:29:52,000
We're not doing anything with integer,

416
00:29:52,000 --> 00:29:55,000
so we need to print it or something like that.

417
00:29:55,000 --> 00:29:58,000
Yeah, exactly.

418
00:29:58,000 --> 00:30:00,000
We'll get an unused variable.

419
00:30:00,000 --> 00:30:02,000
What else is not going to work about this?

420
00:30:02,000 --> 00:30:06,000
I think you said something, Sam. Semicolons.

421
00:30:06,000 --> 00:30:08,000
Yeah, I'm missing those semicolons.

422
00:30:08,000 --> 00:30:14,000
It's going to be a constant thing throughout the course of the term.

423
00:30:14,000 --> 00:30:17,000
The final thing I'll do is I'll put some white space on either side

424
00:30:17,000 --> 00:30:23,000
of this operator here, since that's typically how we do it

425
00:30:23,000 --> 00:30:26,000
according to our style guide.

426
00:30:26,000 --> 00:30:29,000
We've got the midpoint of our array.

427
00:30:29,000 --> 00:30:32,000
Now if we remember back to our algorithm,

428
00:30:32,000 --> 00:30:37,000
what was the second step that we had to do once we have the midpoint?

429
00:30:37,000 --> 00:30:42,000
[Student] If it's greater [inaudible].

430
00:30:42,000 --> 00:30:48,000
Yeah, so we have to do some sort of comparison, and what are we comparing here?

431
00:30:48,000 --> 00:30:53,000
You said if it is greater than. What is it in that sentence referring to?

432
00:30:53,000 --> 00:30:57,000
The number that comes up, if that's greater than the midpoint, then go up to the array?

433
00:30:57,000 --> 00:31:05,000
Exactly, so the number that comes up when we—

434
00:31:05,000 --> 00:31:10,000
The needle, so we're comparing to the needle,

435
00:31:10,000 --> 00:31:12,000
and what are we comparing against the needle?

436
00:31:12,000 --> 00:31:15,000
Because the needle is what we're looking for.

437
00:31:15,000 --> 00:31:18,000
We're comparing it to get to the midpoint.

438
00:31:18,000 --> 00:31:21,000
>> But does it make sense to check to see

439
00:31:21,000 --> 00:31:27,000
if needle = midpoint?

440
00:31:27,000 --> 00:31:32,000
Does that make sense?

441
00:31:32,000 --> 00:31:35,000
Does anybody disagree?

442
00:31:35,000 --> 00:31:40,000
Let's give it a try, if (needle == midpoint).

443
00:31:40,000 --> 00:31:42,000
[Student] Do printf you found it.

444
00:31:42,000 --> 00:31:51,000
[Nate] Printf("We found it!\n");

445
00:31:51,000 --> 00:31:56,000
Otherwise—I'm going to start doing something different here.

446
00:31:56,000 --> 00:32:00,000
I'm going to start putting braces around if statements all the time

447
00:32:00,000 --> 00:32:05,000
just because if we add more stuff, then

448
00:32:05,000 --> 00:32:07,000
we don't get the compilers.

449
00:32:07,000 --> 00:32:09,000
Yeah, Sam. You've got a point.

450
00:32:09,000 --> 00:32:12,000
The problem is that midpoint represents a position in the array,

451
00:32:12,000 --> 00:32:15,000
but you can get it to represent the value in that position of the array.

452
00:32:15,000 --> 00:32:17,000
That's a great point.

453
00:32:17,000 --> 00:32:19,000
Did everybody hear what Sam said?

454
00:32:19,000 --> 00:32:22,000
He said that midpoint as is

455
00:32:22,000 --> 00:32:28,000
represents just a position in the array, but it's not the actual element in the array.

456
00:32:28,000 --> 00:32:30,000
If you think about the code as written right now,

457
00:32:30,000 --> 00:32:35,000
if we look at this array down here, which has 8 elements in it,

458
00:32:35,000 --> 00:32:39,000
what is the value of midpoint going to be in this function?

459
00:32:39,000 --> 00:32:41,000
[Student] 4.

460
00:32:41,000 --> 00:32:45,000
[Nate] 4.

461
00:32:45,000 --> 00:32:51,000
If we look for the number 4—

462
00:32:51,000 --> 00:32:54,000
and we can just run this code and put a little sad face in here

463
00:32:54,000 --> 00:32:58,000
because we didn't find it—if we run this code

464
00:32:58,000 --> 00:33:04,000
as is right now, uploading it, building, let me scroll down,

465
00:33:04,000 --> 00:33:09,000
and if we look for the number 4,

466
00:33:09,000 --> 00:33:18,000
we found it, but we didn't get this to printf yes.

467
00:33:18,000 --> 00:33:23,000
One reason is that we didn't return true,

468
00:33:23,000 --> 00:33:26,000
but did we really find the number 4?

469
00:33:26,000 --> 00:33:28,000
And Sam is saying no.

470
00:33:28,000 --> 00:33:31,000
What did we find?

471
00:33:31,000 --> 00:33:35,000
We really found the midpoint, which if we look at the array down here,

472
00:33:35,000 --> 00:33:38,000
it's going to be the element at index 4 that we're looking at,

473
00:33:38,000 --> 00:33:42,000
which is 23.

474
00:33:42,000 --> 00:33:46,000
>> How do we actually get that element at the midpoint

475
00:33:46,000 --> 00:33:48,000
and not just the midpoint itself?

476
00:33:48,000 --> 00:33:52,000
[Student] We would enter char or something?

477
00:33:52,000 --> 00:33:55,000
What would that do, just out of curiosity?

478
00:33:55,000 --> 00:33:57,000
Can you elaborate a little more?

479
00:33:57,000 --> 00:34:02,000
You have to transform the position into the number,

480
00:34:02,000 --> 00:34:05,000
so you've got to make some connection—I think it's char, but it might not be.

481
00:34:05,000 --> 00:34:07,000
Yeah, that's a good point.

482
00:34:07,000 --> 00:34:12,000
We've been doing a lot of this converting positions into chars, these characters,

483
00:34:12,000 --> 00:34:14,000
in the first two problem sets.

484
00:34:14,000 --> 00:34:18,000
It turns out that here, this is almost similar to

485
00:34:18,000 --> 00:34:24,000
accessing the ith character within a string, if that makes sense.

486
00:34:24,000 --> 00:34:30,000
Here we want to access the midpoint element.

487
00:34:30,000 --> 00:34:34,000
How do we do that?

488
00:34:34,000 --> 00:34:39,000
Kevin, do you have any suggestions how we might do that?

489
00:34:39,000 --> 00:34:44,000
You could do haystack, open bracket, mid, closed bracket.

490
00:34:44,000 --> 00:34:46,000
Can you write that for us?

491
00:34:46,000 --> 00:34:51,000
Save it in here, and we'll pull that up.

492
00:34:51,000 --> 00:34:56,000
We're looking at this line 9,

493
00:34:56,000 --> 00:34:59,000
and we're realizing that we don't want to compare the needle to the midpoint,

494
00:34:59,000 --> 00:35:03,000
but instead, we want to compare the needle

495
00:35:03,000 --> 00:35:07,000
to the element at position midpoint within our haystack array.

496
00:35:07,000 --> 00:35:10,000
Cool.

497
00:35:10,000 --> 00:35:12,000
There we go.

498
00:35:12,000 --> 00:35:15,000
Yeah, that looks pretty good, if (needle == haystack[midpoint]).

499
00:35:15,000 --> 00:35:18,000
We found it.

500
00:35:18,000 --> 00:35:22,000
Now if we run the code—we'll back up a little bit—

501
00:35:22,000 --> 00:35:26,000
it compiles, it runs, and now if we look for 4,

502
00:35:26,000 --> 00:35:30,000
we didn't find it because now we're actually getting the number 23.

503
00:35:30,000 --> 00:35:33,000
We're getting the value 23, and that's what we're comparing to our needle.

504
00:35:33,000 --> 00:35:35,000
But that's good. That's a step in the right direction.

505
00:35:35,000 --> 00:35:37,000
>> That's what we're trying to do.

506
00:35:37,000 --> 00:35:40,000
We're not trying to compare the needle against positions in the array

507
00:35:40,000 --> 00:35:44,000
but rather against the actual elements in the array.

508
00:35:44,000 --> 00:35:49,000
If we look back again now at the next step in our algorithm,

509
00:35:49,000 --> 00:35:51,000
what is the next step?

510
00:35:51,000 --> 00:35:57,000
Leila already mentioned it briefly.

511
00:35:57,000 --> 00:36:00,000
[Student] Check to see if it's greater than or less than and then decide which way to move.

512
00:36:00,000 --> 00:36:03,000
[Nate] Yeah, so how would we do that?

513
00:36:03,000 --> 00:36:07,000
Can you put in some—I'll save this revision,

514
00:36:07,000 --> 00:36:13,000
and then if you put in some lines that will do that.

515
00:36:13,000 --> 00:36:15,000
Yeah, Charlotte.>>I have a question.

516
00:36:15,000 --> 00:36:19,000
Shouldn't it be midpoint - 1 because the first thing is

517
00:36:19,000 --> 00:36:26,000
it's 0 indexed, so if we put 4, that's not actually the character we're looking for?

518
00:36:26,000 --> 00:36:30,000
Yes, and the other problem with that is—

519
00:36:30,000 --> 00:36:35,000
that's a great catch, because what is going to end up happening possibly

520
00:36:35,000 --> 00:36:42,000
if we keep moving and we don't ever adjust initially?

521
00:36:42,000 --> 00:36:46,000
I guess what we might end up doing is trying to access

522
00:36:46,000 --> 00:36:49,000
the element at the 8th position of the array,

523
00:36:49,000 --> 00:36:53,000
which in this case doesn't exist.

524
00:36:53,000 --> 00:36:56,000
We will want to do some sort of accounting for the fact

525
00:36:56,000 --> 00:36:59,000
that we have some zero indexing.

526
00:36:59,000 --> 00:37:05,000
[Charlotte] Sorry, I meant midpoint - 1 in the square brackets.

527
00:37:05,000 --> 00:37:08,000
We can do that.

528
00:37:08,000 --> 00:37:10,000
We'll come back to this issue in just a bit.

529
00:37:10,000 --> 00:37:13,000
Once we start to get to the actual looping,

530
00:37:13,000 --> 00:37:16,000
that's when we'll really see this come into play.

531
00:37:16,000 --> 00:37:21,000
For the time being, we can do this, but you're totally right.

532
00:37:21,000 --> 00:37:28,000
That zero indexing will have an effect that we need to account for.

533
00:37:28,000 --> 00:37:30,000
Let's see.

534
00:37:30,000 --> 00:37:34,000
>> How is the greater than and less than—?

535
00:37:34,000 --> 00:37:36,000
[Student] I get how to do the greater than and less than part.

536
00:37:36,000 --> 00:37:41,000
I just wasn't sure what to print if you find that it is less than the haystack midpoint or greater than.

537
00:37:41,000 --> 00:37:43,000
Here I can save what I've—

538
00:37:43,000 --> 00:37:47,000
[Nate] Yeah, if you save what you've got, and we'll pull it up.

539
00:37:47,000 --> 00:37:49,000
There we go.

540
00:37:49,000 --> 00:37:51,000
[Student] And I put question marks for what I didn't know.

541
00:37:51,000 --> 00:37:54,000
[Nate] That looks great.

542
00:37:54,000 --> 00:37:58,000
Here we've got question marks because we still don't know

543
00:37:58,000 --> 00:38:06,000
what we're going to quite do yet.

544
00:38:06,000 --> 00:38:12,000
What would we want to do—oops, we've got some braces all funky on us.

545
00:38:12,000 --> 00:38:15,000
We'll correct these braces.

546
00:38:15,000 --> 00:38:19,000
There we go.

547
00:38:19,000 --> 00:38:22,000
And so what do we want to do, according to our algorithm,

548
00:38:22,000 --> 00:38:27,000
if we don't find the needle?

549
00:38:27,000 --> 00:38:32,000
Say in the case that the needle is less than what we're looking at. Kevin.

550
00:38:32,000 --> 00:38:34,000
Only look at the left half.

551
00:38:34,000 --> 00:38:40,000
Right, so we'll put a comment in here that says "look at left half."

552
00:38:40,000 --> 00:38:46,000
And if the needle is greater than the haystack at the midpoint, what do we want to do?

553
00:38:46,000 --> 00:38:48,000
[Student] Then you look at the right half.

554
00:38:48,000 --> 00:38:53,000
Look at the right half, "look at right half."

555
00:38:53,000 --> 00:38:58,000
Not too shabby.

556
00:38:58,000 --> 00:39:05,000
Okay, so at this point, things are looking pretty good.

557
00:39:05,000 --> 00:39:13,000
The problem with the code as written is what?

558
00:39:13,000 --> 00:39:15,000
[Student] You don't have endpoints for the halves.

559
00:39:15,000 --> 00:39:18,000
Right, we don't have endpoints for the halves.

560
00:39:18,000 --> 00:39:20,000
We also are only going to go through this once.

561
00:39:20,000 --> 00:39:23,000
We're only going to look at one midpoint.

562
00:39:23,000 --> 00:39:27,000
Either the element is there, or it's not.

563
00:39:27,000 --> 00:39:34,000
In order to complete this, we'll need to do some sort of repetition.

564
00:39:34,000 --> 00:39:39,000
We need to keep repeating until we find that

565
00:39:39,000 --> 00:39:43,000
either the element is in there because we've narrowed down and finally found it,

566
00:39:43,000 --> 00:39:46,000
or it's not in there because we've looked through all of the things

567
00:39:46,000 --> 00:39:52,000
in the appropriate halves of the array and found that nothing is in there.

568
00:39:52,000 --> 00:39:56,000
>> Whenever we've got this repetition going on, what are we going to use?

569
00:39:56,000 --> 00:39:58,000
[Student] A loop.

570
00:39:58,000 --> 00:40:00,000
Some sort of loop. Yes.

571
00:40:00,000 --> 00:40:03,000
[Student] Can we do a do-while loop and have it do that and then while

572
00:40:03,000 --> 00:40:10,000
the needle does not equal—I'm not sure where I was going with that.

573
00:40:10,000 --> 00:40:18,000
But kind of like do that as long as it doesn't equal the value that the user input.

574
00:40:18,000 --> 00:40:21,000
Yeah, so let's see, how might this write itself?

575
00:40:21,000 --> 00:40:23,000
You said let's use a do-while loop.

576
00:40:23,000 --> 00:40:26,000
Where does the do start?

577
00:40:26,000 --> 00:40:33,000
[Student] Right after the size/2.

578
00:40:33,000 --> 00:40:42,000
[Nate] Okay, and what are we going to do?

579
00:40:42,000 --> 00:40:44,000
We'll fill in the while later.

580
00:40:44,000 --> 00:40:46,000
What are we going to do?

581
00:40:46,000 --> 00:40:49,000
[Student] Don't we want to do all the stuff we have in the if portion?

582
00:40:49,000 --> 00:40:52,000
[Nate] Do all this stuff, great.

583
00:40:52,000 --> 00:40:55,000
Copy and paste.

584
00:40:55,000 --> 00:40:59,000
Oh, man.

585
00:40:59,000 --> 00:41:03,000
Let's see if this works, if we can tab this over.

586
00:41:03,000 --> 00:41:08,000
Beautiful.

587
00:41:08,000 --> 00:41:16,000
Okay, and we save this so you guys have it.

588
00:41:16,000 --> 00:41:21,000
All right, and we are going to do this while—

589
00:41:21,000 --> 00:41:25,000
what was the while condition you were after?

590
00:41:25,000 --> 00:41:31,000
[Student] While the needle does not equal, so like the exclamation point.

591
00:41:31,000 --> 00:41:37,000
But I'm not sure exactly what that is yet.

592
00:41:37,000 --> 00:41:39,000
[Nate] Yeah, this is one way to do it.

593
00:41:39,000 --> 00:41:41,000
Sam, do you have a comment?

594
00:41:41,000 --> 00:41:43,000
[Sam] I remembered when I looked at the videos,

595
00:41:43,000 --> 00:41:48,000
I took a screenshot of one of the—like when we did the pseudocode for it,

596
00:41:48,000 --> 00:41:52,000
there was some relationship between max and min.

597
00:41:52,000 --> 00:41:58,000
I think it was something like if max is ever less than min.

598
00:41:58,000 --> 00:42:00,000
Got it.

599
00:42:00,000 --> 00:42:04,000
[Sam] Or like if max is not less than min or something like that,

600
00:42:04,000 --> 00:42:06,000
because that would mean that you've searched everything.

601
00:42:06,000 --> 00:42:13,000
>> Yeah, so what does it sound like max and min were referring to?

602
00:42:13,000 --> 00:42:16,000
[Sam] Values that—integers that are going to change

603
00:42:16,000 --> 00:42:18,000
relative to where we put the midpoint.

604
00:42:18,000 --> 00:42:20,000
Exactly.

605
00:42:20,000 --> 00:42:24,000
[Sam] At that point, it's going to [inaudible] calculate the max and min.

606
00:42:24,000 --> 00:42:29,000
Midpoint is this max and min idea.

607
00:42:29,000 --> 00:42:35,000
Does that make sense to folks?

608
00:42:35,000 --> 00:42:39,000
If we were to start looking at how we're going to do this iteration,

609
00:42:39,000 --> 00:42:43,000
you're totally right that we want to use some sort of do-while loop.

610
00:42:43,000 --> 00:42:49,000
But I guess if we remember what's going on at the spot of this array

611
00:42:49,000 --> 00:42:53,000
and what's actually happening—I'm going to write over here—

612
00:42:53,000 --> 00:42:58,000
at the very first iteration of binary search, we have—

613
00:42:58,000 --> 00:43:05,000
I'm going to use b and e to denote the beginning.

614
00:43:05,000 --> 00:43:10,000
And then the end of our array.

615
00:43:10,000 --> 00:43:14,000
We know that the beginning is at 4 right over here,

616
00:43:14,000 --> 00:43:18,000
and we know that the end is at 108.

617
00:43:18,000 --> 00:43:23,000
Say we're searching for the number 15.

618
00:43:23,000 --> 00:43:27,000
The first time we do this, like we saw earlier,

619
00:43:27,000 --> 00:43:30,000
the midpoint is either going to be 16 or 23

620
00:43:30,000 --> 00:43:34,000
depending on how we calculate things out.

621
00:43:34,000 --> 00:43:37,000
Since evenly dividing in the middle would give us this space

622
00:43:37,000 --> 00:43:42,000
between 16 and 23, we can't evenly divide it

623
00:43:42,000 --> 00:43:47,000
or divide it and get at a true midpoint.

624
00:43:47,000 --> 00:43:49,000
We'll look at 16.

625
00:43:49,000 --> 00:43:55,000
We'll realize "Hey, 16 > 15 that we're looking for."

626
00:43:55,000 --> 00:43:59,000
To then look at the left half of the array

627
00:43:59,000 --> 00:44:03,000
what we'll end up doing is discarding

628
00:44:03,000 --> 00:44:07,000
this entire upper portion

629
00:44:07,000 --> 00:44:16,000
and saying, "Okay, now our endpoint is going to be here."

630
00:44:16,000 --> 00:44:22,000
The next iteration of our loop, we're now looking at this array,

631
00:44:22,000 --> 00:44:25,000
effectively having discarded this portion because now

632
00:44:25,000 --> 00:44:30,000
if we're taking the midpoint to be the difference between the beginning and the end,

633
00:44:30,000 --> 00:44:34,000
we find our midpoint to be 8,

634
00:44:34,000 --> 00:44:40,000
which we can then test 8 to see where it is in relation to the number we're looking for,

635
00:44:40,000 --> 00:44:44,000
15, find that 15 is greater,

636
00:44:44,000 --> 00:44:49,000
so we have to move to the right portion of the list,

637
00:44:49,000 --> 00:44:51,000
which we know because we're humans, and we can see it.

638
00:44:51,000 --> 00:44:54,000
We know that the right portion is going to be where we find it,

639
00:44:54,000 --> 00:45:01,000
but the computer doesn't know that, so what we'll do is we'll actually

640
00:45:01,000 --> 00:45:04,000
have this go up, and now the beginning and the end

641
00:45:04,000 --> 00:45:11,000
are the same spot, so the midpoint becomes the only number in the list at that point,

642
00:45:11,000 --> 00:45:16,000
which is 15, and we've found it.

643
00:45:16,000 --> 00:45:21,000
Does that shed some light on where this whole max and min notation is going,

644
00:45:21,000 --> 00:45:24,000
keeping track of the endpoints of the array in order to figure out

645
00:45:24,000 --> 00:45:35,000
how to narrow things down?

646
00:45:35,000 --> 00:45:42,000
>> What would happen if this weren't equal to 15 now?

647
00:45:42,000 --> 00:45:52,000
What if we were looking for 15 and, instead, this number were also 16?

648
00:45:52,000 --> 00:45:54,000
We'd say, "Oh, it's greater.

649
00:45:54,000 --> 00:45:57,000
We want to go back to the left."

650
00:45:57,000 --> 00:46:01,000
And we'd move our e to the right,

651
00:46:01,000 --> 00:46:06,000
at which point we have an endpoint that would be conflicting.

652
00:46:06,000 --> 00:46:09,000
It wouldn't be able to search for any more elements

653
00:46:09,000 --> 00:46:13,000
because now we have our endpoint and our beginning point,

654
00:46:13,000 --> 00:46:16,000
our max and our min, are now flipped.

655
00:46:16,000 --> 00:46:23,000
We search through the entire array. We can't find anything.

656
00:46:23,000 --> 00:46:27,000
That's the point at which we'd want to say, "Okay, we're going to stop this algorithm.

657
00:46:27,000 --> 00:46:34,000
We haven't found anything. We know it's not in here."

658
00:46:34,000 --> 00:46:36,000
How is this going?

659
00:46:36,000 --> 00:46:40,000
[Student] How exactly does the computer switch the end?

660
00:46:40,000 --> 00:46:45,000
How does the end end up before the beginning?

661
00:46:45,000 --> 00:46:48,000
The end ends up before the beginning

662
00:46:48,000 --> 00:46:54,000
because of the math that we're going to do each time we do this.

663
00:46:54,000 --> 00:47:00,000
The way we swap is if you look at the very first time we do this swap

664
00:47:00,000 --> 00:47:03,000
where we have the beginning at 4 and the end

665
00:47:03,000 --> 00:47:13,000
all the way down at 108 and our midpoint, say, at 16—

666
00:47:13,000 --> 00:47:20,000
I'm going to reset this back to 15—if we're looking for the 15,

667
00:47:20,000 --> 00:47:25,000
we knew that what we did when we checked the 16 and saw that it was greater

668
00:47:25,000 --> 00:47:28,000
and wanted to discard the entire right portion of the list,

669
00:47:28,000 --> 00:47:36,000
we saw that what we wanted to do is move this e right here.

670
00:47:36,000 --> 00:47:44,000
Effectively, the e got moved to one before the midpoint.

671
00:47:44,000 --> 00:47:48,000
Likewise, when we did this iteration of the algorithm

672
00:47:48,000 --> 00:47:51,000
and the midpoint was at 8,

673
00:47:51,000 --> 00:47:55,000
we found that 8 < 15, so we wanted to move the b

674
00:47:55,000 --> 00:48:00,000
one past the midpoint.

675
00:48:00,000 --> 00:48:07,000
Now, the beginning and the end are both together at this 15.

676
00:48:07,000 --> 00:48:10,000
>> If we'd been happening to look for some other value, not 15,

677
00:48:10,000 --> 00:48:14,000
or if this 15 had instead been a 16,

678
00:48:14,000 --> 00:48:20,000
we would have found that the e we want to move one before the midpoint.

679
00:48:20,000 --> 00:48:33,000
Now the e would be there flipped less than the b.

680
00:48:33,000 --> 00:48:39,000
Let's walk through how we actually end up coding this algorithm.

681
00:48:39,000 --> 00:48:44,000
We know that we want to have this midpoint calculation.

682
00:48:44,000 --> 00:48:48,000
We know also that we want to track the beginning and the end of the array

683
00:48:48,000 --> 00:48:51,000
of our current array so we can figure out

684
00:48:51,000 --> 00:48:56,000
where this left half of the list is and where the right half of the list is.

685
00:48:56,000 --> 00:49:03,000
We do that with either begin and end,

686
00:49:03,000 --> 00:49:07,000
or we can call them min and max.

687
00:49:07,000 --> 00:49:10,000
I'll use begin and end this time.

688
00:49:10,000 --> 00:49:15,000
When we begin, if we look back at our example down here,

689
00:49:15,000 --> 00:49:20,000
our beginning was set to the very beginning of the array, as natural.

690
00:49:20,000 --> 00:49:25,000
What index was this? What should our begin be?

691
00:49:25,000 --> 00:49:27,000
Daniel.

692
00:49:27,000 --> 00:49:30,000
[Daniel] Haystack[0].

693
00:49:30,000 --> 00:49:37,000
[Nate] Yeah, so we could set it equal to haystack[0].

694
00:49:37,000 --> 00:49:40,000
The problem, though, is that this gives us not the position of the first element.

695
00:49:40,000 --> 00:49:45,000
It gives us the index of the first element or the actual value at that first position.

696
00:49:45,000 --> 00:49:47,000
[Student] That will convert to .20?

697
00:49:47,000 --> 00:49:52,000
[Nate] What this will do is—well, it won't do any converting.

698
00:49:52,000 --> 00:49:56,000
What it will do is it will store a 4 in begin,

699
00:49:56,000 --> 00:49:59,000
and then it will be hard to make comparisons against begin

700
00:49:59,000 --> 00:50:03,000
because begin will be holding the value of 4,

701
00:50:03,000 --> 00:50:06,000
which is the beginning of our array,

702
00:50:06,000 --> 00:50:08,000
but we want to track the indices in the array

703
00:50:08,000 --> 00:50:11,000
as opposed to the values.

704
00:50:11,000 --> 00:50:17,000
We'll actually use a 0, like that.

705
00:50:17,000 --> 00:50:20,000
For the end of the array—Charlotte brought this up a little earlier.

706
00:50:20,000 --> 00:50:23,000
This is where we'll take into account the zero indexing.

707
00:50:23,000 --> 00:50:25,000
>> Charlotte, what's the end of the array?

708
00:50:25,000 --> 00:50:28,000
What is the index of the end?

709
00:50:28,000 --> 00:50:30,000
[Charlotte] Size - 1.

710
00:50:30,000 --> 00:50:32,000
Yeah, and which size should we use?

711
00:50:32,000 --> 00:50:35,000
Should we use capital size or lowercase size?

712
00:50:35,000 --> 00:50:37,000
Capital size.

713
00:50:37,000 --> 00:50:42,000
In this case, we could use capital size.

714
00:50:42,000 --> 00:50:45,000
If we wanted this function to be portable

715
00:50:45,000 --> 00:50:48,000
and use this function in other programs,

716
00:50:48,000 --> 00:50:50,000
we can actually use lowercase size.

717
00:50:50,000 --> 00:50:52,000
It's fine too.

718
00:50:52,000 --> 00:51:01,000
But Charlotte is totally right that we want to have size - 1.

719
00:51:01,000 --> 00:51:03,000
At this point—

720
00:51:03,000 --> 00:51:05,000
[Student] How is it that you can use uppercase size?

721
00:51:05,000 --> 00:51:07,000
How is it that we could use uppercase size?

722
00:51:07,000 --> 00:51:13,000
It turns out that these #defines are really,

723
00:51:13,000 --> 00:51:19,000
under the hood, a text like find and replace, if that makes sense.

724
00:51:19,000 --> 00:51:24,000
When you compile your code, the preprocessing phase

725
00:51:24,000 --> 00:51:27,000
of the compiler goes through the file,

726
00:51:27,000 --> 00:51:31,000
and it looks for everywhere that you've written capital size,

727
00:51:31,000 --> 00:51:39,000
and it replaces that text literally with an 8, just like that.

728
00:51:39,000 --> 00:51:42,000
In that sense, this is very different from a variable.

729
00:51:42,000 --> 00:51:45,000
It doesn't take up any space in memory.

730
00:51:45,000 --> 00:51:52,000
It's a simple text replace trick.

731
00:51:52,000 --> 00:51:57,000
In this case, we're going to use size.

732
00:51:57,000 --> 00:52:01,000
From here we do want to do some sort of repetition,

733
00:52:01,000 --> 00:52:03,000
and we're on the right track with our do-while loop.

734
00:52:03,000 --> 00:52:08,000
We want to do something until a condition doesn't hold anymore,

735
00:52:08,000 --> 00:52:12,000
and as we saw earlier, we saw that that condition

736
00:52:12,000 --> 00:52:19,000
was indeed that we don't want the end

737
00:52:19,000 --> 00:52:24,000
to be less than the begin.

738
00:52:24,000 --> 00:52:26,000
>> This is our stopping condition.

739
00:52:26,000 --> 00:52:35,000
If this occurs, we want to stop and declare like, "Hey, we haven't found anything."

740
00:52:35,000 --> 00:52:43,000
To express this, we do want to use some sort of loop.

741
00:52:43,000 --> 00:52:49,000
In this case, would it be a do-while loop, a for loop, a while loop?

742
00:52:49,000 --> 00:52:51,000
We have a do-while loop here.

743
00:52:51,000 --> 00:52:53,000
Do you guys like that approach?

744
00:52:53,000 --> 00:52:59,000
Do you think we should try a different approach?

745
00:52:59,000 --> 00:53:01,000
Kevin, any thoughts?

746
00:53:01,000 --> 00:53:06,000
We could have a while loop because we know maximum

747
00:53:06,000 --> 00:53:11,000
would be greater than min at the start anyways.

748
00:53:11,000 --> 00:53:14,000
Yeah, so there's no initialization that needs to happen.

749
00:53:14,000 --> 00:53:17,000
Those do-while loops are great when you have to initialize something

750
00:53:17,000 --> 00:53:21,000
before then testing, whereas here

751
00:53:21,000 --> 00:53:26,000
we know that we're not going to keep reinitializing both begin and end

752
00:53:26,000 --> 00:53:28,000
every round of the loop.

753
00:53:28,000 --> 00:53:32,000
We know that we want to initialize them, then check our condition.

754
00:53:32,000 --> 00:53:38,000
In this case, I'll actually go with a simple while loop.

755
00:53:38,000 --> 00:53:44,000
It turns out that do-while loops are used fairly infrequently.

756
00:53:44,000 --> 00:53:49,000
A lot of places don't even teach do while loops.

757
00:53:49,000 --> 00:53:53,000
They're good for handling user input, so we've seen a lot of them thus far.

758
00:53:53,000 --> 00:53:59,000
But normal for and while loops are a lot more common.

759
00:53:59,000 --> 00:54:03,000
It turns out that this condition as written

760
00:54:03,000 --> 00:54:09,000
won't really do us much good, and why is that?

761
00:54:09,000 --> 00:54:11,000
I'm sorry, I don't know your name.

762
00:54:11,000 --> 00:54:13,000
I'm Jerry.>>Sorry?

763
00:54:13,000 --> 00:54:15,000
It's B-O-R-U-I.

764
00:54:15,000 --> 00:54:18,000
Oh, okay.

765
00:54:18,000 --> 00:54:23,000
I don't see you on my list.

766
00:54:23,000 --> 00:54:26,000
Oh, it's because—oh, that makes sense.

767
00:54:26,000 --> 00:54:31,000
Do you have an idea of why this while loop might not work as intended,

768
00:54:31,000 --> 00:54:38,000
as written with the condition?

769
00:54:38,000 --> 00:54:43,000
[Jerry] You mean like you want all the stuff after it into the—?

770
00:54:43,000 --> 00:54:46,000
Yeah, so that's one.

771
00:54:46,000 --> 00:54:49,000
We might have to put all of this stuff into the while loop, which is totally true.

772
00:54:49,000 --> 00:54:55,000
The other thing that's a little more problematic, though, is that this condition doesn't work.

773
00:54:55,000 --> 00:54:57,000
[Student] You need to flip it.

774
00:54:57,000 --> 00:55:04,000
Right, so this condition won't ever be true initially the way we talked about it.

775
00:55:04,000 --> 00:55:08,000
We want to do something until end < begin,

776
00:55:08,000 --> 00:55:13,000
but we want to do something while

777
00:55:13,000 --> 00:55:21,000
begin ≤ end.

778
00:55:21,000 --> 00:55:24,000
>> There's that reversal of the logic there.

779
00:55:24,000 --> 00:55:27,000
I'm guilty of making those mistakes all the time.

780
00:55:27,000 --> 00:55:31,000
[Student] Why does it have to be less than or equal to?

781
00:55:31,000 --> 00:55:33,000
Because do you remember the case that we got to

782
00:55:33,000 --> 00:55:36,000
where there was only one element, and we were down,

783
00:55:36,000 --> 00:55:43,000
and we were looking at just the 15 in our array?

784
00:55:43,000 --> 00:55:47,000
And our beginning and our end were the same element.

785
00:55:47,000 --> 00:55:50,000
We want to make sure that we handle that case.

786
00:55:50,000 --> 00:55:54,000
If we did a straight less than,

787
00:55:54,000 --> 00:55:58,000
we would only be able to get down to a 2-element array.

788
00:55:58,000 --> 00:56:06,000
Once we got down to that last element, if that were our element, we'd never find it.

789
00:56:06,000 --> 00:56:10,000
Now here, we can do exactly like you were saying.

790
00:56:10,000 --> 00:56:15,000
We can start plopping stuff right into the middle of our while loop.

791
00:56:15,000 --> 00:56:20,000
We can plop in our midpoint.

792
00:56:20,000 --> 00:56:24,000
We can take all of these if statements,

793
00:56:24,000 --> 00:56:30,000
pull them out of this do-while loop,

794
00:56:30,000 --> 00:56:34,000
plop them in,

795
00:56:34,000 --> 00:56:39,000
clean things up a little bit,

796
00:56:39,000 --> 00:56:48,000
and I'll go ahead and save this revision.

797
00:56:48,000 --> 00:56:53,000
And at this point, we're getting pretty close.

798
00:56:53,000 --> 00:56:55,000
Sam.

799
00:56:55,000 --> 00:56:58,000
I think you also have to have int midpoint = size - 1 / 2.

800
00:56:58,000 --> 00:57:01,000
Got it, size - 1 / 2.

801
00:57:01,000 --> 00:57:05,000
Is there anything else we need to change about that line?

802
00:57:05,000 --> 00:57:10,000
That was a good catch.

803
00:57:10,000 --> 00:57:14,000
>> What does size do? Are we ever changing size?

804
00:57:14,000 --> 00:57:17,000
In order to keep the line like this, we have to change the size.

805
00:57:17,000 --> 00:57:21,000
We have to change the size every time we go around the for loop.

806
00:57:21,000 --> 00:57:25,000
But remember when we were going through our example just a little bit earlier,

807
00:57:25,000 --> 00:57:30,000
and we had the beginning at 4

808
00:57:30,000 --> 00:57:33,000
and the end all the way over at 108?

809
00:57:33,000 --> 00:57:35,000
How did we calculate the midpoint?

810
00:57:35,000 --> 00:57:38,000
Were we using the size?

811
00:57:38,000 --> 00:57:40,000
Or we were using begin and end instead?

812
00:57:40,000 --> 00:57:42,000
It's the difference between the end and the beginning.

813
00:57:42,000 --> 00:57:50,000
Exactly, and how exactly should I write that, Charlotte?

814
00:57:50,000 --> 00:57:52,000
Just end - begin.

815
00:57:52,000 --> 00:57:55,000
You wouldn't need to do the - 1

816
00:57:55,000 --> 00:57:58,000
because the - 1 has been included in the end and the begin already.

817
00:57:58,000 --> 00:58:00,000
[Nate] Great, you're totally right.

818
00:58:00,000 --> 00:58:03,000
We don't have to do the - 1 because that - 1 has been included

819
00:58:03,000 --> 00:58:08,000
and accounted for when we initialize the end variable.

820
00:58:08,000 --> 00:58:11,000
>> Is there anything else I need to do syntactically to have this line make sense?

821
00:58:11,000 --> 00:58:13,000
[Student] Plus begin.>>Plus begin?

822
00:58:13,000 --> 00:58:15,000
[Student] At the end.

823
00:58:15,000 --> 00:58:20,000
Because it's only calculated half the length.

824
00:58:20,000 --> 00:58:26,000
You need to add the begin.

825
00:58:26,000 --> 00:58:31,000
[Nate] What would this calculate for us?

826
00:58:31,000 --> 00:58:35,000
If we think about end on this very first iteration of the loop,

827
00:58:35,000 --> 00:58:40,000
end is going to be in position index 7.

828
00:58:40,000 --> 00:58:43,000
Begin is in position 0.

829
00:58:43,000 --> 00:58:47,000
Remember, we're looking for either

830
00:58:47,000 --> 00:58:52,000
position 3 or position 4.

831
00:58:52,000 --> 00:58:56,000
If we look at this math, just to make it a little more tangible,

832
00:58:56,000 --> 00:59:02,000
put some numbers here, we have 7, 0,

833
00:59:02,000 --> 00:59:10,000
so 7 - 0, and then / 2

834
00:59:10,000 --> 00:59:19,000
is 3 in integer division, that is.

835
00:59:19,000 --> 00:59:26,000
Then do we need to then add back our begin?

836
00:59:26,000 --> 00:59:28,000
We don't in this case.

837
00:59:28,000 --> 00:59:31,000
On the very first iteration, it will be fine because begin is 0.

838
00:59:31,000 --> 00:59:36,000
But as we progress, we do really all just need

839
00:59:36,000 --> 00:59:42,000
end - begin / 2.

840
00:59:42,000 --> 00:59:46,000
There's one other trick here, and that is namely one of precedence.

841
00:59:46,000 --> 00:59:49,000
[Student] Do we need parentheses?

842
00:59:49,000 --> 00:59:53,000
[Nate] Exactly, and that's because if we don't put these parentheses,

843
00:59:53,000 --> 00:59:58,000
then this line will be interpreted instead

844
00:59:58,000 --> 01:00:09,000
as (end) - (begin / 2), which we definitely don't want.

845
01:00:09,000 --> 01:00:11,000
Watch out for those precedence rules.

846
01:00:11,000 --> 01:00:15,000
[Student] Why isn't it end + begin?

847
01:00:15,000 --> 01:00:17,000
Why isn't it end + begin?

848
01:00:17,000 --> 01:00:19,000
[Student] Why is it not that?

849
01:00:19,000 --> 01:00:24,000
Why would it be +?

850
01:00:24,000 --> 01:00:26,000
I think you're right.

851
01:00:26,000 --> 01:00:28,000
[Student] Because it's average?

852
01:00:28,000 --> 01:00:31,000
[Nate] End + begin, you're totally right.

853
01:00:31,000 --> 01:00:34,000
Wow, I totally goofed. You're right.

854
01:00:34,000 --> 01:00:39,000
If we were doing the minus, we would want to add the begin back in.

855
01:00:39,000 --> 01:00:43,000
In this case, you're very right that we want to take the average of the two,

856
01:00:43,000 --> 01:00:45,000
so we do want to add them, as opposed to subtract them.

857
01:00:45,000 --> 01:00:49,000
[Student] It would also work if you did end - begin / 2 + begin.

858
01:00:49,000 --> 01:00:55,000
It would if we do—I believe so.

859
01:00:55,000 --> 01:01:00,000
>> For example, if we were looking at begin,

860
01:01:00,000 --> 01:01:04,000
and we shifted it over here

861
01:01:04,000 --> 01:01:08,000
to the 15.

862
01:01:08,000 --> 01:01:12,000
Now begin is at position 2.

863
01:01:12,000 --> 01:01:15,000
End is at position 7.

864
01:01:15,000 --> 01:01:21,000
If we subtract them, we get 5.

865
01:01:21,000 --> 01:01:24,000
Divide that by 2, we get 2.

866
01:01:24,000 --> 01:01:27,000
And then we add 2 back in,

867
01:01:27,000 --> 01:01:30,000
and that gets us to the 4th position,

868
01:01:30,000 --> 01:01:33,000
which is right here, which is the midpoint.

869
01:01:33,000 --> 01:01:36,000
[Student] Do we need to take care of wrapping?

870
01:01:36,000 --> 01:01:39,000
In what sense do we need to take care of wrapping?

871
01:01:39,000 --> 01:01:43,000
If the sum or the difference between

872
01:01:43,000 --> 01:01:45,000
depending on how we do it is not an even number.

873
01:01:45,000 --> 01:01:49,000
Then the computer gets confused whether when it's 2.5;

874
01:01:49,000 --> 01:01:52,000
do you move to the left or to the right to determine which is the midpoint?

875
01:01:52,000 --> 01:01:54,000
Got it.

876
01:01:54,000 --> 01:01:56,000
It turns out that with integer division,

877
01:01:56,000 --> 01:01:59,000
we don't ever get these floating point numbers.

878
01:01:59,000 --> 01:02:01,000
We never get the decimal.

879
01:02:01,000 --> 01:02:04,000
It's totally discarded.

880
01:02:04,000 --> 01:02:08,000
If you have a computer divide two int variables,

881
01:02:08,000 --> 01:02:11,000
and one is 7, and the other is 2,

882
01:02:11,000 --> 01:02:13,000
you won't get 3.5 as a result.

883
01:02:13,000 --> 01:02:16,000
It will get 3.

884
01:02:16,000 --> 01:02:19,000
The remainder will be discarded, so it's effectively rounding—

885
01:02:19,000 --> 01:02:24,000
not a round but rather a floor, if you guys are familiar with that in math,

886
01:02:24,000 --> 01:02:27,000
where you completely discard the decimal,

887
01:02:27,000 --> 01:02:31,000
and so you're essentially truncating it down to the nearest

888
01:02:31,000 --> 01:02:33,000
whole position, to the nearest whole number.

889
01:02:33,000 --> 01:02:38,000
[Student] But then that's problematic because if you have an array of 7 elements

890
01:02:38,000 --> 01:02:43,000
then that automatically takes the 3rd element out of the midpoint instead of the 4th.

891
01:02:43,000 --> 01:02:46,000
How do we deal with that?

892
01:02:46,000 --> 01:02:49,000
It's problematic because if we had an array of 7,

893
01:02:49,000 --> 01:02:54,000
it would pick the 3rd instead of the 4th.

894
01:02:54,000 --> 01:02:56,000
Could you explain a little more?

895
01:02:56,000 --> 01:02:59,000
[Student] Because if you have 7 elements then the 4th element

896
01:02:59,000 --> 01:03:04,000
would be the midpoint, right?

897
01:03:04,000 --> 01:03:07,000
Remember your comment about being zero indexed, though.

898
01:03:07,000 --> 01:03:10,000
[Student] Yeah, so in position 3. That would be the midpoint.

899
01:03:10,000 --> 01:03:12,000
Yeah.

900
01:03:12,000 --> 01:03:16,000
Oh, okay. I see what you mean.

901
01:03:16,000 --> 01:03:19,000
It's kind of weird, as we get used to this whole notion of

902
01:03:19,000 --> 01:03:22,000
getting rid of decimals.

903
01:03:22,000 --> 01:03:26,000
That's a great point.

904
01:03:26,000 --> 01:03:30,000
Let's finish this up.

905
01:03:30,000 --> 01:03:32,000
We've calculated our midpoint.

906
01:03:32,000 --> 01:03:37,000
>> We're testing to see if our needle is equal to the middle value.

907
01:03:37,000 --> 01:03:41,000
We're printing that we found it, but really, what do we want to do in this situation?

908
01:03:41,000 --> 01:03:46,000
We've found it, so we want to let the caller know that we found it.

909
01:03:46,000 --> 01:03:49,000
We've got a function that's a boolean typed function.

910
01:03:49,000 --> 01:03:54,000
The way we signal to the caller of our function that we're ready to go

911
01:03:54,000 --> 01:03:58,000
is we say, "Hey, this is true."

912
01:03:58,000 --> 01:04:00,000
How would we do that, Kevin?

913
01:04:00,000 --> 01:04:02,000
You're nodding your head.>>[Kevin] Add return true.

914
01:04:02,000 --> 01:04:06,000
[Nate] Exactly, return true.

915
01:04:06,000 --> 01:04:12,000
Now, if it's not equal, how would we look at the left half?

916
01:04:12,000 --> 01:04:16,000
Any ideas?

917
01:04:16,000 --> 01:04:18,000
Stella, any ideas?

918
01:04:18,000 --> 01:04:21,000
You need to set a new position for end.

919
01:04:21,000 --> 01:04:23,000
Yeah.

920
01:04:23,000 --> 01:04:29,000
So we have to do position of midpoint  - the end.

921
01:04:29,000 --> 01:04:33,000
Great.

922
01:04:33,000 --> 01:04:36,000
We need to set a new position for the end

923
01:04:36,000 --> 01:04:38,000
to look at the left half.

924
01:04:38,000 --> 01:04:41,000
This was what we talked about before where

925
01:04:41,000 --> 01:04:44,000
I keep going back to this example.

926
01:04:44,000 --> 01:04:50,000
I have the begin here, and then I have the end all the way over here.

927
01:04:50,000 --> 01:04:53,000
>> Again, if we're looking for 15, and our midpoint is at 16,

928
01:04:53,000 --> 01:04:56,000
and we realize, "Oops, 16 is greater.

929
01:04:56,000 --> 01:04:59,000
We want to move to the left half."

930
01:04:59,000 --> 01:05:02,000
We would then move the end to the 15,

931
01:05:02,000 --> 01:05:06,000
and we do that by taking one away from the midpoint

932
01:05:06,000 --> 01:05:09,000
and setting that as our new end.

933
01:05:09,000 --> 01:05:12,000
Likewise, if we want to look at the right half, how would we do that?

934
01:05:12,000 --> 01:05:14,000
Do you have an idea?

935
01:05:14,000 --> 01:05:22,000
[Student] You just set begin to midpoint + 1.

936
01:05:22,000 --> 01:05:24,000
[Nate] Great.

937
01:05:24,000 --> 01:05:29,000
And now in the case that we don't find anything,

938
01:05:29,000 --> 01:05:32,000
does that get taken care of for us?

939
01:05:32,000 --> 01:05:36,000
Daniel, does that get taken care of for us?

940
01:05:36,000 --> 01:05:38,000
[Daniel] No.

941
01:05:38,000 --> 01:05:40,000
[Nate] If we make it through the entire array and we don't find anything,

942
01:05:40,000 --> 01:05:42,000
where would that be taken care of, or should we take care of it?

943
01:05:42,000 --> 01:05:44,000
[Daniel] The while condition.

944
01:05:44,000 --> 01:05:48,000
[Nate] Yeah, the while condition, exactly.

945
01:05:48,000 --> 01:05:51,000
It will take care of going through the entire array if we don't find anything.

946
01:05:51,000 --> 01:05:53,000
This while loop will end.

947
01:05:53,000 --> 01:05:56,000
We will never have encountered this condition,

948
01:05:56,000 --> 01:06:03,000
and we can return false.

949
01:06:03,000 --> 01:06:10,000
We can also leave this if in here like this

950
01:06:10,000 --> 01:06:14,000
because if this if statement is true,

951
01:06:14,000 --> 01:06:16,000
and our function will return,

952
01:06:16,000 --> 01:06:21,000
and so we'll essentially abort this function at this point

953
01:06:21,000 --> 01:06:24,000
when we return true.

954
01:06:24,000 --> 01:06:28,000
But what happens with this structure here?

955
01:06:28,000 --> 01:06:34,000
Will this work entirely, or is there some logical flaw in there?

956
01:06:34,000 --> 01:06:37,000
>> There is some logical flaw in there, with the way it's set up.

957
01:06:37,000 --> 01:06:40,000
What might it be?

958
01:06:40,000 --> 01:06:43,000
[Student] Why do you need the - and + 1s?

959
01:06:43,000 --> 01:06:47,000
That sets our array up to be our new left half and right half.

960
01:06:47,000 --> 01:06:51,000
[Student] But why couldn't you do it without the - 1s and + 1s?

961
01:06:51,000 --> 01:06:53,000
[Nate] We could set it equal to the midpoint?

962
01:06:53,000 --> 01:07:04,000
What might be problematic about that?

963
01:07:04,000 --> 01:07:08,000
[Student] I guess it's inefficient because you're checking a value that's already been checked.

964
01:07:08,000 --> 01:07:11,000
[Nate] Exactly, so Sam is totally right.

965
01:07:11,000 --> 01:07:15,000
If you set the end and the begin equal to the midpoint

966
01:07:15,000 --> 01:07:18,000
instead of - 1 and + 1 reflectively,

967
01:07:18,000 --> 01:07:22,000
at some point in the future we'll end up checking the midpoint again.

968
01:07:22,000 --> 01:07:26,000
[Student] I started the pset, and then I had something like that

969
01:07:26,000 --> 01:07:30,000
where I forgot the + 1, and it got stuck in an infinite loop.

970
01:07:30,000 --> 01:07:34,000
Right, because at some point you're never going to get begin and end

971
01:07:34,000 --> 01:07:39,000
to actually overlap.

972
01:07:39,000 --> 01:07:41,000
Cool.

973
01:07:41,000 --> 01:07:44,000
There's one more logical flaw, and that is that this should definitely be

974
01:07:44,000 --> 01:07:48,000
an else if.

975
01:07:48,000 --> 01:07:55,000
Why might that be?

976
01:07:55,000 --> 01:07:59,000
>> The reason is if it's not an else if—did you see it, Kevin?

977
01:07:59,000 --> 01:08:02,000
[Kevin] Yeah, because you're changing the end point.

978
01:08:02,000 --> 01:08:05,000
[Nate] Exactly.

979
01:08:05,000 --> 01:08:07,000
We're changing the endpoint,

980
01:08:07,000 --> 01:08:12,000
and if it's written like this—we'll make spaces between—

981
01:08:12,000 --> 01:08:14,000
it will check this case.

982
01:08:14,000 --> 01:08:18,000
This case, if it succeeds, will abort out of the function.

983
01:08:18,000 --> 01:08:21,000
Then it will check this next case,

984
01:08:21,000 --> 01:08:24,000
and if this succeeds, it will adjust the endpoint,

985
01:08:24,000 --> 01:08:28,000
and then it will continue on and check this case.

986
01:08:28,000 --> 01:08:31,000
But at this point, we don't want it to continue checking.

987
01:08:31,000 --> 01:08:35,000
Fortunately, we haven't reset the midpoint here,

988
01:08:35,000 --> 01:08:39,000
and we know that this case won't succeed.

989
01:08:39,000 --> 01:08:44,000
But we definitely want to put the else if in there

990
01:08:44,000 --> 01:08:48,000
even though that might—in this case

991
01:08:48,000 --> 01:08:52,000
since we're not adjusting the midpoint, would that make a difference?

992
01:08:52,000 --> 01:08:54,000
No, because these cases are all exclusive.

993
01:08:54,000 --> 01:08:58,000
Again, my bad.

994
01:08:58,000 --> 01:09:01,000
We don't, I think, need this else if.

995
01:09:01,000 --> 01:09:05,000
We can give it a try and run it and see what happens.

996
01:09:05,000 --> 01:09:08,000
Building, an error occurred.

997
01:09:08,000 --> 01:09:12,000
It's probably because I left these b's and e's in here.

998
01:09:12,000 --> 01:09:14,000
Do I have any more of those up at the top?

999
01:09:14,000 --> 01:09:16,000
It doesn't look like it.

1000
01:09:16,000 --> 01:09:20,000
We zoom out, build,

1001
01:09:20,000 --> 01:09:24,000
there it goes, so now if we search for 15,

1002
01:09:24,000 --> 01:09:28,000
yes.

1003
01:09:28,000 --> 01:09:30,000
Let me zoom in.

1004
01:09:30,000 --> 01:09:33,000
15, yes. We can run it again.

1005
01:09:33,000 --> 01:09:36,000
Uploading source code, building, running.

1006
01:09:36,000 --> 01:09:41,000
We can search for something like 13,

1007
01:09:41,000 --> 01:09:45,000
and we don't get anything printing out, so it's not finding that for us.

1008
01:09:45,000 --> 01:09:51,000
That's great, because it's not in our list.

1009
01:09:51,000 --> 01:09:53,000
>> We are now out of time.

1010
01:09:53,000 --> 01:09:55,000
That's going to be it for this week.

1011
01:09:55,000 --> 01:10:00,000
Thanks for joining, and see you later.

1012
01:10:00,000 --> 01:10:02,000
>> [CS50.TV]