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

2
00:00:06,370 --> 00:00:08,150
>> JASON Hirschhorn: Välkommen
till vecka tre, alla.

3
00:00:08,150 --> 00:00:11,650
Vi har en hektisk men spännande
avsnitt framför oss.

4
00:00:11,650 --> 00:00:17,010
Så först, därför att vi har gjort vissa
framsteg med kursen men vi fortfarande

5
00:00:17,010 --> 00:00:20,570
har en hel del att lära kvar att göra, jag är
ska visa er några resurser

6
00:00:20,570 --> 00:00:24,160
som skulle visa sig vara oerhört
hjälp eftersom du inte bara vända din

7
00:00:24,160 --> 00:00:28,130
Problemet ställer, men också smälta alla
det material vi ger er i

8
00:00:28,130 --> 00:00:30,800
föreläsningar och kortfilmer och avsnitt.

9
00:00:30,800 --> 00:00:34,790
>> Sen ska vi spendera de första 20
till 25 minuters avsnitt gå över

10
00:00:34,790 --> 00:00:38,630
GDB, som du kan eller inte kan ha
används vid denna punkt, men det är en

11
00:00:38,630 --> 00:00:42,570
otroligt användbart verktyg som kommer att
hjälpa dig att felsöka dina program.

12
00:00:42,570 --> 00:00:46,060
Många av er kanske har använt printf i
mitt i ditt program att räkna

13
00:00:46,060 --> 00:00:47,430
vad en variabel uppgick.

14
00:00:47,430 --> 00:00:52,060
GDB är ännu bättre än printf och
inte skruva upp din kod eftersom du

15
00:00:52,060 --> 00:00:53,320
köra det på en körbar fil.

16
00:00:53,320 --> 00:00:56,500
Så går vi över 10 mest användbara
kommandon du behöver för GDB, och vi är

17
00:00:56,500 --> 00:01:00,540
kommer att gå på en övning tillsammans så
i problem set tre och framåt, du

18
00:01:00,540 --> 00:01:03,320
kan använda GDB för att felsöka
dina program.

19
00:01:03,320 --> 00:01:06,420
Och slutligen kommer vi att gå igenom några
sortering och sökning algoritmer

20
00:01:06,420 --> 00:01:10,590
som du såg på föreläsning, och vi är
kommer att faktiskt kod, inte bara

21
00:01:10,590 --> 00:01:17,360
pseudokod, men kod binär sökning,
bubbla sortera och val av sort.

22
00:01:17,360 --> 00:01:20,090
>> Så först, jag vill gå
över resurserna.

23
00:01:20,090 --> 00:01:23,530
Detta är en omfattande lista, och det är
mindre typsnitt eftersom jag hade mycket att

24
00:01:23,530 --> 00:01:24,390
passar på här.

25
00:01:24,390 --> 00:01:26,950
Men dessa kommer inte bara hjälpa dig,
igen, med problemsamlingar och

26
00:01:26,950 --> 00:01:30,760
smälta information du lärt dig, men
definitivt, kom frågesport tid, dessa kommer

27
00:01:30,760 --> 00:01:32,130
vara otroligt hjälpsamma.

28
00:01:32,130 --> 00:01:34,700
Så först, konstaterar föreläsningen.

29
00:01:34,700 --> 00:01:39,480
Om du går till cs50.net/lectures och
bläddra till vecka och dag,

30
00:01:39,480 --> 00:01:43,120
ser du att det finns noteringar för varje
lecture, vilket inte är helt enkelt en

31
00:01:43,120 --> 00:01:47,250
transkript, men en redigerad version av
vad som angavs i föreläsning med kod

32
00:01:47,250 --> 00:01:49,610
strängar och andra hjälp tidbits.

33
00:01:49,610 --> 00:01:52,220
Jag rekommenderar starkt att gå över dem.

34
00:01:52,220 --> 00:01:55,340
Och sedan också, det finns källkod
tillgängliga från varje föreläsning.

35
00:01:55,340 --> 00:02:00,050
Och återigen, kommer dessa bilder också vara
tillgängligt på cs50.net/sections

36
00:02:00,050 --> 00:02:01,480
i kväll.

37
00:02:01,480 --> 00:02:06,860
>> Så andra är shortsen varje vecka som
täcker ämnen, vanligtvis 5 till 15

38
00:02:06,860 --> 00:02:08,090
minuter i längd.

39
00:02:08,090 --> 00:02:12,310
Och de som förhoppningsvis kommer att ge dig en
bra primer på olika ämnen.

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

41
00:02:12,870 --> 00:02:16,370
och detta är helt ny här
år - är study.cs50.net.

42
00:02:16,370 --> 00:02:20,110
Om du inte har kollat ​​upp det, jag
rekommenderar starkt att du gör det.

43
00:02:20,110 --> 00:02:21,100
Du får välja ett ämne.

44
00:02:21,100 --> 00:02:23,040
Vi har massor av frågor om det.

45
00:02:23,040 --> 00:02:24,770
Så till exempel, väljer du Funktioner.

46
00:02:24,770 --> 00:02:27,270
Det ger dig några diabilder
och noterar på funktioner.

47
00:02:27,270 --> 00:02:31,190
De är faktiskt de bilder som TF
uppmuntras att använda under vår

48
00:02:31,190 --> 00:02:32,710
presentationer i avsnitt.

49
00:02:32,710 --> 00:02:35,040
Det finns också tips och tricks för att hantera
med funktioner, och det finns

50
00:02:35,040 --> 00:02:37,290
övnings problem som hjälper
du arbetar med funktioner.

51
00:02:37,290 --> 00:02:41,500
Vi ger dig också länkar till korta på
funktioner och de tider som fungerar

52
00:02:41,500 --> 00:02:42,750
har kommit upp i föreläsningen.

53
00:02:42,750 --> 00:02:46,550
Så study.cs50.net, helt ny här
år, en fantastisk resurs.

54
00:02:46,550 --> 00:02:52,180
>> Nästa, jag har människan, som är den manuella
kommando som du kan köra på

55
00:02:52,180 --> 00:02:52,770
kommandorad.

56
00:02:52,770 --> 00:02:57,880
Så om du har några frågor om en
kommando, till exempel, rand, som vi

57
00:02:57,880 --> 00:03:00,900
mötte förra veckan under avsnitt
och du har förmodligen stött på i

58
00:03:00,900 --> 00:03:05,380
ditt problem inställd när man går igenom
generera kod, men om du skriver man

59
00:03:05,380 --> 00:03:09,980
rand, får du den sida som
berättar allt om rand.

60
00:03:09,980 --> 00:03:14,040
Det ger dig vad som krävs, det
parametrar som krävs, samt avkastning

61
00:03:14,040 --> 00:03:16,530
typ och en kort beskrivning
av denna funktion.

62
00:03:16,530 --> 00:03:17,500
>> Så kolla rand.

63
00:03:17,500 --> 00:03:22,270
Det kan vara en liten ordrik och förvirrande,
så ibland tycker jag att

64
00:03:22,270 --> 00:03:26,150
helt enkelt googla det jag vill veta är
det bästa sättet att hitta svaret.

65
00:03:26,150 --> 00:03:27,940
Så öva med Google.

66
00:03:27,940 --> 00:03:28,600
Få bra på Google.

67
00:03:28,600 --> 00:03:30,600
Det kommer att bli din bästa vän.

68
00:03:30,600 --> 00:03:34,300
>> Förutom Google, om du inte kan hitta det
på Google, cs50.net/discuss, det är

69
00:03:34,300 --> 00:03:35,550
diskussionsforumet.

70
00:03:35,550 --> 00:03:39,390
Chanserna är om du har en fråga, en
av dina 700 + kamrater också har att

71
00:03:39,390 --> 00:03:42,110
fråga och kan ha bett
det redan i diskutera

72
00:03:42,110 --> 00:03:43,540
forum och få den besvarad.

73
00:03:43,540 --> 00:03:48,130
Så om du har en vanlig fråga eller
du har en fråga som du tror

74
00:03:48,130 --> 00:03:52,300
kanske andra människor kanske har stött på,
kolla cs50.net/discuss.

75
00:03:52,300 --> 00:03:55,450
>> Slutligen, de två sista, om du vill
prata med en riktig människa, kontor

76
00:03:55,450 --> 00:03:57,770
timmar måndag till fredag.

77
00:03:57,770 --> 00:04:00,850
Det finns även online-kontorstid
för förlängnings studenter.

78
00:04:00,850 --> 00:04:04,370
Och sist men absolut inte minst,
mig, utropstecken.

79
00:04:04,370 --> 00:04:05,960
Ni har alla mina kontaktuppgifter.

80
00:04:05,960 --> 00:04:11,940
Om du behöver något, vänligen aldrig
tveka inte att kontakta mig.

81
00:04:11,940 --> 00:04:14,020
Du är alltid välkommen att göra det.

82
00:04:14,020 --> 00:04:17,490
Mycket få av er har lagt till mig på Gchat,
så det har varit en besvikelse,

83
00:04:17,490 --> 00:04:20,410
men förhoppningsvis som kommer att förändras mellan
detta och nästa avsnitt.

84
00:04:20,410 --> 00:04:22,105
Har du frågor så långt på resurser?

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

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

87
00:04:27,450 --> 00:04:34,280
>> Slutligen, en annan kontakt för
feedback, sayat.me/cs50.

88
00:04:34,280 --> 00:04:37,050
Du kan ge mig anonym respons
om hur jag gör.

89
00:04:37,050 --> 00:04:38,320
Det var riktigt bra förra veckan.

90
00:04:38,320 --> 00:04:41,890
Jag fick ett par kommentarer från er
direkt efter avsnitt, plus från

91
00:04:41,890 --> 00:04:44,750
andra elever som såg det
under veckan, och det

92
00:04:44,750 --> 00:04:46,830
var otroligt bra.

93
00:04:46,830 --> 00:04:50,250
Jag kommer att försöka begränsa min användning av
ordet "söt", men jag ska visa min

94
00:04:50,250 --> 00:04:52,410
entusiasm och spänning
på andra sätt.

95
00:04:52,410 --> 00:04:56,550
Men det fanns andra tilläggs
materiella återkopplingar,

96
00:04:56,550 --> 00:04:57,600
både plus och delta.

97
00:04:57,600 --> 00:05:00,480
Så snälla, jag ger er respons
på dina problemsamlingar.

98
00:05:00,480 --> 00:05:01,790
Känn dig fri att ge mig feedback
på min undervisning.

99
00:05:01,790 --> 00:05:04,010
Jag är här för er.

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

101
00:05:05,270 --> 00:05:07,020
Det är allt jag har för
det första avsnittet.

102
00:05:07,020 --> 00:05:08,565
Är det någon som har någon
frågor hittills?

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

104
00:05:12,370 --> 00:05:14,640
Och jag har en notering om
kontrollcentralen.

105
00:05:14,640 --> 00:05:21,200
Förlängnings studenter har messaged mig
säger att de inte får något ljud,

106
00:05:21,200 --> 00:05:23,870
men det är utanför min makt för att fixa.

107
00:05:23,870 --> 00:05:25,280
Så förhoppningsvis blir det
lösas inom kort.

108
00:05:25,280 --> 00:05:28,850
Om du tittar på nätet, hej,
men du kan inte höra mig.

109
00:05:28,850 --> 00:05:33,860
>> Så först, ska vi
att gå igenom GDB.

110
00:05:33,860 --> 00:05:37,100
GDB, som jag antydde tidigare,
är ett felsökningsverktyg

111
00:05:37,100 --> 00:05:39,040
mycket bättre än printf.

112
00:05:39,040 --> 00:05:44,700
Så för att komma igång med GDB, killar, om
du vill öppna upp din apparat

113
00:05:44,700 --> 00:05:49,070
och ta den fil som jag mailade till dig
tidigare - den här filen kommer också att

114
00:05:49,070 --> 00:05:51,940
tillgänglig online på lite -

115
00:05:51,940 --> 00:05:55,700
och kör GDB. / namnet på filen.

116
00:05:55,700 --> 00:05:58,580
Först, naturligtvis, måste du kompilera
fil eftersom GDB fungerar bara på

117
00:05:58,580 --> 00:05:59,890
körbara filer.

118
00:05:59,890 --> 00:06:02,300
>> Men om du någonsin vill starta
GDB, det första du gör,

119
00:06:02,300 --> 00:06:04,550
du kör GDB. / Caesar.

120
00:06:04,550 --> 00:06:08,340
Så det är namnet på det program som vi är
kommer att gå med det just nu.

121
00:06:08,340 --> 00:06:12,810
Så jag kommer att skriva att Caesar, som
kommer att ge mig en körbar fil

122
00:06:12,810 --> 00:06:14,100
här markeras med grönt.

123
00:06:14,100 --> 00:06:19,250
Och sedan ska jag köra GDB. / Cesar.

124
00:06:19,250 --> 00:06:19,810
>> Och där du går.

125
00:06:19,810 --> 00:06:24,540
Du ser att vi har en text talar om för mig
om den version av GDB, ger mig

126
00:06:24,540 --> 00:06:27,570
viss garantiinformation, och då vi
har BNP-prompten, som ser sorterar

127
00:06:27,570 --> 00:06:29,350
av som vår kommandoraden,
men du ser att det är öppet

128
00:06:29,350 --> 00:06:32,510
Paren, GDB, nära Paren.

129
00:06:32,510 --> 00:06:36,520
Innan vi fortsätter och felsöka den här filen
som jag skickade till er alla, låt oss titta på

130
00:06:36,520 --> 00:06:40,220
några användbara kommandon så vi har en känsla
av vad vi kommer att täcka.

131
00:06:40,220 --> 00:06:45,060
>> Dessa kommandon visas här i
ordning som jag vanligtvis använder dem.

132
00:06:45,060 --> 00:06:50,230
Så jag startar mitt program genom att köra
GBD. / Namnet på programmet,

133
00:06:50,230 --> 00:06:51,360
i det här fallet, Caesar.

134
00:06:51,360 --> 00:06:57,430
Och sedan det första jag gör 99,9%
av tiden är typ rast menar.

135
00:06:57,430 --> 00:06:59,070
Det sätter en brytpunkt vid huvud.

136
00:06:59,070 --> 00:07:03,260
I huvudsak, vad du gör det
är programmet kommer att stanna vid

137
00:07:03,260 --> 00:07:06,100
huvud så att du kan börja granska den linje
för rad, snarare än att köra alla

138
00:07:06,100 --> 00:07:07,040
vägen igenom.

139
00:07:07,040 --> 00:07:09,730
Du kan bryta vid olika
din kod, men viktigaste är i allmänhet en

140
00:07:09,730 --> 00:07:11,870
bra ställe att börja.

141
00:07:11,870 --> 00:07:14,840
>> Nästa kommando jag kör är körning.

142
00:07:14,840 --> 00:07:17,400
Det startar programmet körs, och
Om du måste ange kommandoraden

143
00:07:17,400 --> 00:07:19,090
argument, kör du det kommandot.

144
00:07:19,090 --> 00:07:20,500
Kör med argumenten.

145
00:07:20,500 --> 00:07:25,000
Så eftersom vi går över en version
av C, som är det program ni

146
00:07:25,000 --> 00:07:26,160
skrev för pset två -

147
00:07:26,160 --> 00:07:29,880
den här, naturligtvis, har en del buggar
i det att vi förhoppningsvis hittar -

148
00:07:29,880 --> 00:07:32,810
vi ska köra köra med några kommandot
line argument eftersom Caesar,

149
00:07:32,810 --> 00:07:34,860
som ni vet per problemet
ställa spec, tar lite

150
00:07:34,860 --> 00:07:36,380
kommandoradsargument.

151
00:07:36,380 --> 00:07:40,000
>> Nästa par kommandon, nästa
man faktiskt kallas nästa.

152
00:07:40,000 --> 00:07:42,470
Att man tar dig rad för rad
genom ditt program.

153
00:07:42,470 --> 00:07:45,800
Så slår n sedan Enter tar dig
till nästa rad, verkställande

154
00:07:45,800 --> 00:07:46,880
föregående rad.

155
00:07:46,880 --> 00:07:49,440
Steg inte bara tar dig till
nästa rad, men det

156
00:07:49,440 --> 00:07:51,070
tar dig inuti funktioner.

157
00:07:51,070 --> 00:07:54,310
Så om du har skrivit en funktion i
din kod, eller om du vill utforska en

158
00:07:54,310 --> 00:07:57,820
att jag, till exempel, kan du träffa er, och
snarare än att gå till nästa rad av

159
00:07:57,820 --> 00:08:02,390
filen som du går igenom höger
nu, kommer du faktiskt kliva in

160
00:08:02,390 --> 00:08:04,670
denna funktion och se dess kod.

161
00:08:04,670 --> 00:08:12,300
>> List visar, i mycket användarvänlig
format, de 10-tal linjer runt

162
00:08:12,300 --> 00:08:14,940
var du är i din kod
så du kan faktiskt se filen

163
00:08:14,940 --> 00:08:17,810
i stället för att byta tillbaka och
tillbaka mellan olika vyer.

164
00:08:17,810 --> 00:08:21,890
Print är som printf,
som namnet antyder.

165
00:08:21,890 --> 00:08:24,020
Det visar vad en variabel är lika.

166
00:08:24,020 --> 00:08:25,870
>> Info lokalbefolkningen är riktigt bra.

167
00:08:25,870 --> 00:08:27,740
Detta är en specialversion av tryck.

168
00:08:27,740 --> 00:08:31,770
Info lokalbefolkningen visar dig alla de lokala
variabler, skriver ut dem alla ut för dig

169
00:08:31,770 --> 00:08:33,380
som finns tillgängliga.

170
00:08:33,380 --> 00:08:36,360
Så jag i allmänhet, snarare än att behöva
skriva ut de fyra variablerna som jag är

171
00:08:36,360 --> 00:08:39,929
nyfiken på om jag är i en for-slinga för
exempel, jag bara skriva info lokalbefolkningen,

172
00:08:39,929 --> 00:08:43,470
och det kommer att visa mig vad min disk i
är lika, samt den array som jag är

173
00:08:43,470 --> 00:08:45,130
arbetar med jämlikar.

174
00:08:45,130 --> 00:08:47,530
>> Slutligen, fortsätt.

175
00:08:47,530 --> 00:08:49,300
Skriva paus stoppar dig
vid brytpunkten.

176
00:08:49,300 --> 00:08:51,380
Du kan gå igenom rad för
linje med nästa och steg.

177
00:08:51,380 --> 00:08:55,640
Fortsätt kör programmet till din nästa
bryta punkt eller till det att hela om

178
00:08:55,640 --> 00:08:57,180
det finns inga fler brytpunkter.

179
00:08:57,180 --> 00:09:00,060
Inaktivera tar bort brytpunkter om du
beslutade paus vid huvud var

180
00:09:00,060 --> 00:09:01,890
olämpligt, du vill
ställa in den någon annanstans.

181
00:09:01,890 --> 00:09:05,090
Och slutligen q, sluta, spårar ur GDB.

182
00:09:05,090 --> 00:09:10,784
>> Så detta program. / Caesar, vi kommer
att titta igenom just nu och vi

183
00:09:10,784 --> 00:09:13,490
ska använda GDB för att hitta
buggar i det här programmet.

184
00:09:13,490 --> 00:09:18,110
Jag körde det här programmet tidigare med
Kontrollera 50, och jag fick en rynka pannan.

185
00:09:18,110 --> 00:09:22,310
Allt det existerade, det sammanställas, det
passerade en hel del av testerna, men för

186
00:09:22,310 --> 00:09:27,950
någon anledning har den inte passera den femte
testet, svarvning BARFOO, versaler, till

187
00:09:27,950 --> 00:09:33,350
E-D-U-I-R-R, versaler,
med användning av tre som en nyckel.

188
00:09:33,350 --> 00:09:34,090
Jag kom ganska nära.

189
00:09:34,090 --> 00:09:35,410
Jag fick med en bokstav.

190
00:09:35,410 --> 00:09:37,340
Så det finns några små misstag i här.

191
00:09:37,340 --> 00:09:38,070
Jag har tittat igenom min kod.

192
00:09:38,070 --> 00:09:38,850
Jag kunde inte lista ut det.

193
00:09:38,850 --> 00:09:41,740
Förhoppningsvis kan ni hjälpa mig
lista ut vad felet är.

194
00:09:41,740 --> 00:09:44,610
>> Så det är fel att vi är
efter.

195
00:09:44,610 --> 00:09:46,090
Låt oss gå in i GDB.

196
00:09:46,090 --> 00:09:51,100
Återigen, jag kör GDB. / Caesar,
så nu är vi i GDB.

197
00:09:51,100 --> 00:09:54,290
Och vad är det första
sak jag ska göra?

198
00:09:54,290 --> 00:09:56,680
Jag har just gått in i GDB.

199
00:09:56,680 --> 00:10:00,316
Någon ge mig en bra
kommando för att komma in.

200
00:10:00,316 --> 00:10:01,140
>> STUDENTEN break.

201
00:10:01,140 --> 00:10:01,800
>> JASON Hirschhorn: break.

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

203
00:10:02,900 --> 00:10:03,560
Låt oss skriva det i.

204
00:10:03,560 --> 00:10:06,390
Ni kan titta på upp här eller följ
tillsammans på dina datorer.

205
00:10:06,390 --> 00:10:09,410
Break, och du kommer att se en
brytpunkt fastställdes till -

206
00:10:09,410 --> 00:10:12,340
det ger mig några konstiga minnesadress,
och det ger mig också radnumret.

207
00:10:12,340 --> 00:10:15,310
Om jag skulle se tillbaka på den här filen,
Jag skulle inse att huvud

208
00:10:15,310 --> 00:10:17,700
hände på linje 21.

209
00:10:17,700 --> 00:10:18,950
Vad ska jag köra nästa?

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

211
00:10:22,970 --> 00:10:25,060
Är mitt program körs?

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

213
00:10:25,650 --> 00:10:27,175
Så vad ska jag köra nästa?

214
00:10:27,175 --> 00:10:27,520
>> STUDENT: Kör.

215
00:10:27,520 --> 00:10:28,050
>> JASON Hirschhorn: Kör.

216
00:10:28,050 --> 00:10:30,760
Ska jag köra bara springa, eller bör
Jag lägger en del andra saker i?

217
00:10:30,760 --> 00:10:31,960
>> STUDENT: Kör med argumentet.

218
00:10:31,960 --> 00:10:33,320
>> JASON Hirschhorn: Kör med
kommandoargument.

219
00:10:33,320 --> 00:10:36,420
Och eftersom jag felsökning av en mycket specifik
fall, ska jag ange att

220
00:10:36,420 --> 00:10:37,120
kommandoradsargumentet.

221
00:10:37,120 --> 00:10:42,290
Så jag kör tre, som är, återigen,
utmatningen jag fick från Check 50.

222
00:10:42,290 --> 00:10:44,240
Starta programmet.

223
00:10:44,240 --> 00:10:45,420
Vi går igenom ett par rader.

224
00:10:45,420 --> 00:10:47,700
Du kommer nu se att vi är på rad 21.

225
00:10:47,700 --> 00:10:49,200
Hur vet jag att vi är på rad 21?

226
00:10:49,200 --> 00:10:52,170
Därför att om man tittar till vänster
mitt terminalfönster, där

227
00:10:52,170 --> 00:10:53,120
det står linje 21.

228
00:10:53,120 --> 00:10:57,010
Och det ger mig, faktiskt, det
kod som är vid linjen 21.

229
00:10:57,010 --> 00:10:58,440
Så jag misspoke tidigare.

230
00:10:58,440 --> 00:10:59,770
Huvud är faktiskt inte på linje 21.

231
00:10:59,770 --> 00:11:02,000
Huvud är ett par rader över 21.

232
00:11:02,000 --> 00:11:04,300
Men på rad 21, det är
där vi bryter.

233
00:11:04,300 --> 00:11:06,280
Denna kodrad har
ännu inte verkställts.

234
00:11:06,280 --> 00:11:06,890
Det är viktigt.

235
00:11:06,890 --> 00:11:09,120
Linjen som du ser har inte
utförts ännu.

236
00:11:09,120 --> 00:11:12,650
Det är nästa kodrad
du är på väg att köra.

237
00:11:12,650 --> 00:11:15,860
>> Så nästa rad, eftersom ni är
förmodligen bekant med, är detta

238
00:11:15,860 --> 00:11:20,070
villkor kontroll för att se om jag har
trädde en kommandorad argument.

239
00:11:20,070 --> 00:11:22,140
Och en till i, vad är den andra
en del av det som gör?

240
00:11:22,140 --> 00:11:23,457
Vad är att jag?

241
00:11:23,457 --> 00:11:24,950
>> STUDENT: Ändra det till ett heltal.

242
00:11:24,950 --> 00:11:25,450
>> JASON Hirschhorn: Förlåt?

243
00:11:25,450 --> 00:11:27,400
>> STUDENT: Det ändrar
Argumentet till ett heltal.

244
00:11:27,400 --> 00:11:30,890
>> JASON Hirschhorn: Så en till jag ändrar arg
v1 från en sträng till ett heltal.

245
00:11:30,890 --> 00:11:32,140
Och vad är det kontroll?

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

247
00:11:35,414 --> 00:11:37,112
>> STUDENT: Om det finns en andra
kommandorad argument åt sidan

248
00:11:37,112 --> 00:11:38,100
från att köra programmet.

249
00:11:38,100 --> 00:11:39,460
>> JASON Hirschhorn: Och vad är
den andra halvan av det här

250
00:11:39,460 --> 00:11:41,220
Booleskt uttryck kontroll?

251
00:11:41,220 --> 00:11:42,540
Denna del hit, en till mig?

252
00:11:42,540 --> 00:11:44,080
>> STUDENT: Om det är negativt.

253
00:11:44,080 --> 00:11:45,380
>> JASON Hirschhorn: Att se till vad?

254
00:11:45,380 --> 00:11:47,120
>> STUDENT: Att se till att det
är i själva verket positivt.

255
00:11:47,120 --> 00:11:47,650
>> JASON Hirschhorn: Exakt.

256
00:11:47,650 --> 00:11:50,600
Detta är att kontrollera om det är
negativ, och om det är negativt, jag

257
00:11:50,600 --> 00:11:53,220
har en känsla av nästa rad kanske
ska jag skrika åt användaren.

258
00:11:53,220 --> 00:11:55,930
Så låt oss slå slut att genomföra denna linje.

259
00:11:55,930 --> 00:11:59,925
Vi ser inte att linje som ni
kanske förväntas se skrika på

260
00:11:59,925 --> 00:12:03,030
användare och sedan återvänder, eftersom
denna linje inte köra.

261
00:12:03,030 --> 00:12:03,840
Jag angav 3.

262
00:12:03,840 --> 00:12:06,860
Så jag gjorde faktiskt anger två kommando
line argument, och 3 är

263
00:12:06,860 --> 00:12:07,610
större än noll.

264
00:12:07,610 --> 00:12:09,950
Så vi såg den linjen, avrättades vi,
men vi ville inte gå

265
00:12:09,950 --> 00:12:11,300
inne i om tillståndet.

266
00:12:11,300 --> 00:12:17,060
>> Så nu, nästa, ser jag att jag ställer
int nyckel är lika med en till jag arg v1.

267
00:12:17,060 --> 00:12:18,840
Så det är jag skapa en variabel nyckel.

268
00:12:18,840 --> 00:12:22,450
Så om jag skriver ut nyckeln just nu, eftersom
som gör att du kan se

269
00:12:22,450 --> 00:12:26,040
värde inuti variabel,
nyckel är lika med 47.

270
00:12:26,040 --> 00:12:28,810
Det är konstigt, men naturligtvis,
det beror på att jag har inte

271
00:12:28,810 --> 00:12:30,490
avrättades den linjen ännu.

272
00:12:30,490 --> 00:12:35,880
Så nu om jag slog n, köra den linjen,
och gör utskriftsknapp, kommer nyckeln lika 3,

273
00:12:35,880 --> 00:12:37,740
vilket är vad vi förväntar oss att det till lika.

274
00:12:37,740 --> 00:12:41,170
>> Så återigen, i GDB, den linje du
ser du inte har verk ännu.

275
00:12:41,170 --> 00:12:44,850
Du måste slå n eller s eller ett nummer
av andra kommandon till faktiskt

276
00:12:44,850 --> 00:12:46,610
exekvera den linjen.

277
00:12:46,610 --> 00:12:47,380
Skriv ut nyckeln.

278
00:12:47,380 --> 00:12:48,280
Nyckel s vid 3.

279
00:12:48,280 --> 00:12:49,750
Så långt är allt bra.

280
00:12:49,750 --> 00:12:51,000
String är vanlig text.

281
00:12:51,000 --> 00:12:52,270
Låt oss köra den linjen.

282
00:12:52,270 --> 00:12:53,970
Jag får en sträng från användaren.

283
00:12:53,970 --> 00:12:58,690
>> Låt oss se i min Kontrollera 50, jag
ange BARFOO versaler, så

284
00:12:58,690 --> 00:13:01,330
det är vad jag ska skriva.

285
00:13:01,330 --> 00:13:07,300
Om jag nu skriva ut vanlig text.

286
00:13:07,300 --> 00:13:08,610
Du ser att det är lika med en sträng.

287
00:13:08,610 --> 00:13:11,100
Det ger mig en annan konstig hexadecimal
nummer, men det gör i

288
00:13:11,100 --> 00:13:13,620
faktiskt säga att min sträng är BARFOO.

289
00:13:13,620 --> 00:13:19,308
Om jag ville se vad nyckeln uppgick vid
denna punkt, hur kunde jag kontrollera nyckeln?

290
00:13:19,308 --> 00:13:20,710
>> STUDENTEN Print nyckel.

291
00:13:20,710 --> 00:13:22,010
>> JASON Hirschhorn: Print nyckel, exakt.

292
00:13:22,010 --> 00:13:23,260
Och faktiskt, det finns en genväg.

293
00:13:23,260 --> 00:13:25,910
Om du tröttnar på att skriva ut,
du kan bara skriva sid.

294
00:13:25,910 --> 00:13:28,340
Så p knapp gör exakt samma sak.

295
00:13:28,340 --> 00:13:29,730
Och igen, ser jag att det är lika med 3.

296
00:13:29,730 --> 00:13:34,760
>> Om jag ville ta reda på vad både nyckel
och BARFOO equaled samtidigt

297
00:13:34,760 --> 00:13:37,215
men jag var trött på att skriva varje
ett individuellt, jag

298
00:13:37,215 --> 00:13:38,590
kan skriva info lokalbefolkningen.

299
00:13:38,590 --> 00:13:41,170
Det ger mig viktiga jämlikar 3.

300
00:13:41,170 --> 00:13:42,500
Enkel text motsvarar BARFOO.

301
00:13:42,500 --> 00:13:45,265
Det ger mig också dessa två konstiga saker
upptill, denna variabel i och

302
00:13:45,265 --> 00:13:46,590
denna variabel n.

303
00:13:46,590 --> 00:13:48,460
>> De som faktiskt existerande
i mitt huvudprogram.

304
00:13:48,460 --> 00:13:51,280
Vi har inte stött på dem ännu,
men som en förhandsvisning, som

305
00:13:51,280 --> 00:13:52,880
existerar i mitt för slinga.

306
00:13:52,880 --> 00:13:55,360
Så just nu, de lika lite konstig
siffror, eftersom de inte har

307
00:13:55,360 --> 00:13:58,300
initierats ännu, men de finns kvar
i minnet, så att de bara satt

308
00:13:58,300 --> 00:14:00,220
till några sopor värde.

309
00:14:00,220 --> 00:14:02,890
Men vi ser nyckeln i klartext
text där.

310
00:14:02,890 --> 00:14:06,390
>> Så jag kommer att köra den här linjen,
linje 34, den för slingan.

311
00:14:06,390 --> 00:14:08,220
Vi kommer att hoppa in i
för slinga genom att träffa n..

312
00:14:08,220 --> 00:14:10,050
Och vi är inne i för slingan.

313
00:14:10,050 --> 00:14:11,360
Vi är på vår första kontroll.

314
00:14:11,360 --> 00:14:14,300
Och återigen, bör dessa slags titta
bekant för dig, eftersom det var en

315
00:14:14,300 --> 00:14:18,080
Caesar program som skrevs, men
igen, har något slags bugg.

316
00:14:18,080 --> 00:14:21,940
>> Och nu om jag gör info lokalbefolkningen, eftersom jag är
insidan som för slinga, ser du

317
00:14:21,940 --> 00:14:23,900
att jag är lika med noll, eftersom vi förväntar oss.

318
00:14:23,900 --> 00:14:26,820
Det är vad vi ställa in den till och initieras
det i för slingan.

319
00:14:26,820 --> 00:14:27,560
n är lika med 6.

320
00:14:27,560 --> 00:14:30,700
Det är också rimligt att vi satt
den till strlen av ren text.

321
00:14:30,700 --> 00:14:34,270
Så jag gillar att göra info lokalbefolkningen eller skriv ut
till variabel ofta att se till att

322
00:14:34,270 --> 00:14:36,370
allt är alltid vad
Jag förväntar mig att det lika.

323
00:14:36,370 --> 00:14:39,800
I detta fall är allt
vad jag förväntar mig det lika.

324
00:14:39,800 --> 00:14:41,850
>> Så låt oss börja röra sig genom
detta för slinga.

325
00:14:41,850 --> 00:14:45,715
Linjen jag är på är linje 36, om vanligt
text i är större än ett och vanlig

326
00:14:45,715 --> 00:14:48,540
text i är mindre än eller lika med z.

327
00:14:48,540 --> 00:14:51,880
Jag vet att mitt problem är inte med min första
brev, är det med den andra bokstaven.

328
00:14:51,880 --> 00:14:56,290
Om vi ​​ser tillbaka på Check
50, B går till E böter.

329
00:14:56,290 --> 00:14:59,010
Jag tar det A och lämnar den som
ett A, inte ändra det till D. So

330
00:14:59,010 --> 00:15:00,200
något är fel med
det andra brevet.

331
00:15:00,200 --> 00:15:01,640
Så jag ska flytta
det på en sekund.

332
00:15:01,640 --> 00:15:06,030
>> Men om jag ville kolla vad vanligt
text jag equaled i detta särskilda

333
00:15:06,030 --> 00:15:07,760
fall, jag tycker att det borde vara vad?

334
00:15:07,760 --> 00:15:10,980
Vad ska klartext jag lika i detta
första omgången genom att loopen?

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: Enkel text av I?

338
00:15:16,510 --> 00:15:21,180
Så det borde vara kapital B. Jag, naturligtvis,
är lika med noll, men oformaterad text

339
00:15:21,180 --> 00:15:25,600
bygel noll avslutad bygel motsvarar B
eftersom strängar, som vi såg förra veckan,

340
00:15:25,600 --> 00:15:28,650
är array, så vi får det
första tecknet från det.

341
00:15:28,650 --> 00:15:34,960
Så återigen, om jag skrivas ut vanlig text av
Jag, jag tror faktiskt få karaktären

342
00:15:34,960 --> 00:15:36,560
B. Och det är snyggt, eller hur?

343
00:15:36,560 --> 00:15:40,380
Jag behöver faktiskt inte klartext I.
Det är inte en av de variabler som jag som

344
00:15:40,380 --> 00:15:42,950
eller initieras, men du kan skriva ut
ut en mängd saker

345
00:15:42,950 --> 00:15:45,640
om du skulle vilja.

346
00:15:45,640 --> 00:15:47,340
>> Men låt oss gå igenom.

347
00:15:47,340 --> 00:15:50,050
Om klartext jag är större än A och
klartext I är mindre än eller lika med

348
00:15:50,050 --> 00:15:53,290
Z, helt klart är det sant att vi har
ett kapital B. Jag kommer att köra

349
00:15:53,290 --> 00:15:54,230
lite kommando på det.

350
00:15:54,230 --> 00:15:58,530
Vi såg att matte förra veckan, så vi ska
tar det för givet att det fungerar

351
00:15:58,530 --> 00:16:00,900
rätt enligt Check 50.

352
00:16:00,900 --> 00:16:03,720
>> Dessa klamrar, den första
visade att jag lämnar om

353
00:16:03,720 --> 00:16:07,030
tillstånd, den andra visade
att jag lämnar för loopen.

354
00:16:07,030 --> 00:16:10,400
Och så nu när jag slog Nästa, vi får se
Vi är tillbaka på för slingan igen.

355
00:16:10,400 --> 00:16:11,970
Vi går igenom
för slingan igen.

356
00:16:11,970 --> 00:16:18,110
Låt oss verkligen kliva in i andra
iteration av för slingan och typ

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

358
00:16:20,520 --> 00:16:22,190
>> Så vi är i den andra iterationen
vår för slinga.

359
00:16:22,190 --> 00:16:24,530
Jag är lika med 1, som vi förväntar oss.

360
00:16:24,530 --> 00:16:26,650
N är lika med 6, som vi förväntar oss.

361
00:16:26,650 --> 00:16:28,810
Nyckel lika med 3, som vi förväntar oss.

362
00:16:28,810 --> 00:16:32,625
Och ren text, ser du, är lika med
EARFOO nu, inte BARFOO längre eftersom

363
00:16:32,625 --> 00:16:37,930
i vårt tidigare iterationen, var B
ändras till ett kapital E. Så vi är på väg

364
00:16:37,930 --> 00:16:40,040
att stöta på problem, så detta
är där vi ska

365
00:16:40,040 --> 00:16:41,130
dyka i felsökning.

366
00:16:41,130 --> 00:16:43,365
Men det någon som har några frågor
om vad vi har gjort hittills?

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

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

369
00:16:47,910 --> 00:16:52,710
>> Så vi är på väg att genomföra detta om
tillstånd, klartext fäste jag stängt

370
00:16:52,710 --> 00:16:57,500
fäste större än A och vanlig text jag
mindre än eller lika med Z. Men innan

371
00:16:57,500 --> 00:17:00,450
Jag går in i det, eftersom det är här
Jag vet att mitt misstag är, jag vill peka

372
00:17:00,450 --> 00:17:06,859
ut vanlig text av I. So
låt oss sätta utskrift.

373
00:17:06,859 --> 00:17:12,020
Den gör motsvara tecknet A, så att
verkar så långt är allt gott och väl.

374
00:17:12,020 --> 00:17:14,740
>> Så jag räknar med denna linje per min logik,
denna linje ska vara sant.

375
00:17:14,740 --> 00:17:16,099
Det är en stor bokstav.

376
00:17:16,099 --> 00:17:20,599
Men om jag slog n, vi inser att detta
linje, i själva verket inte köras.

377
00:17:20,599 --> 00:17:22,609
Jag hoppade ner till else if.

378
00:17:22,609 --> 00:17:25,460
Varför hände det?

379
00:17:25,460 --> 00:17:27,480
>> STUDENT: Eftersom du har ditt tillstånd
av vanlig text är större

380
00:17:27,480 --> 00:17:29,130
än A, inte är lika med eller större än.

381
00:17:29,130 --> 00:17:32,260
>> JASON Hirschhorn: Så jag hade min oformaterad text
I är större än A, som inte är större

382
00:17:32,260 --> 00:17:32,850
än eller lika med.

383
00:17:32,850 --> 00:17:38,130
Så klart, gjorde huvudstaden A inte
utlösa detta om tillstånd, och vi gjorde

384
00:17:38,130 --> 00:17:40,520
inte kliva in i det, och vi gjorde
inte göra de nödvändiga ändringarna.

385
00:17:40,520 --> 00:17:41,360
Så det är det, faktiskt.

386
00:17:41,360 --> 00:17:42,920
Jag kom på min bugg.

387
00:17:42,920 --> 00:17:46,775
Jag skulle kunna gå tillbaka i min källfilen,
ändra det, och uppdatera den och

388
00:17:46,775 --> 00:17:47,855
kör Check 50 igen.

389
00:17:47,855 --> 00:17:52,590
>> Men vi får se, bara för pedagogik s
skull, om jag fortsätter att gå.

390
00:17:52,590 --> 00:17:59,580
Den annars om inte köra heller, men
vad stället lika är kommandot

391
00:17:59,580 --> 00:18:00,500
det ändras inte.

392
00:18:00,500 --> 00:18:04,840
Så det har inte förändrats alls, och om jag
skriva ut ren text här, vi får se att gå

393
00:18:04,840 --> 00:18:08,250
genom att för slingan inte gjorde det, i själva verket,
ändra på det andra tecknet alls.

394
00:18:08,250 --> 00:18:09,600
Det är fortfarande en kapital A.

395
00:18:09,600 --> 00:18:12,690
>> Så återigen, debuggade vi våra misstag.

396
00:18:12,690 --> 00:18:17,380
Vi insåg att det inte fanns
viss logik saknas.

397
00:18:17,380 --> 00:18:20,590
Och vi debuggade det i förväg innan
faktiskt köra den linjen,

398
00:18:20,590 --> 00:18:24,320
men du skulle ha märkt hade vi bara
slå på Nästa och hoppa till det annars om,

399
00:18:24,320 --> 00:18:26,710
det innebär att att om villkoret
var inte sant.

400
00:18:26,710 --> 00:18:29,550
Vi har inte, i själva verket får
resultatet förväntas vi.

401
00:18:29,550 --> 00:18:33,240
Så då vi skulle ha genomfört, hade
vi inte varit så klok, att titta på

402
00:18:33,240 --> 00:18:38,510
att om tillstånd och kontrollera om, i själva verket,
våra villkor bör utvärderas till

403
00:18:38,510 --> 00:18:41,150
sant i det aktuella sammanhanget.

404
00:18:41,150 --> 00:18:42,880
>> Det var allt för felsökning av det här programmet.

405
00:18:42,880 --> 00:18:45,340
Är det någon som har några frågor?

406
00:18:45,340 --> 00:18:50,486
Vilket kommando skulle jag slog till sluta GDB?

407
00:18:50,486 --> 00:18:53,900
F: Och då jag blir ombedd,
sluta hur som helst?

408
00:18:53,900 --> 00:18:54,390
Ja eller nej.

409
00:18:54,390 --> 00:18:58,440
Jag ska träffa ja, och jag har slutat GDB.

410
00:18:58,440 --> 00:19:00,860
>> Så det var en snabb primer till GDB.

411
00:19:00,860 --> 00:19:03,430
Faktiskt, i ett verkligt scenario
Jag gjorde detta på kontorstid.

412
00:19:03,430 --> 00:19:06,710
Jag GDBed detta exakt program på
kontorstid med en elev.

413
00:19:06,710 --> 00:19:12,410
Och om vi går tillbaka till de kommandon som vi såg
tidigare, använde vi break, först

414
00:19:12,410 --> 00:19:13,190
sak gjorde vi.

415
00:19:13,190 --> 00:19:16,060
Vi använde springa med kommandoradsargument,
andra saken gjorde vi.

416
00:19:16,060 --> 00:19:18,520
Vi använde bredvid en hel del att flytta
oss genom linjer.

417
00:19:18,520 --> 00:19:20,310
Och återigen, den korta versionen
nästa är n..

418
00:19:20,310 --> 00:19:22,920
Det är inom parentes
i grått på bilden.

419
00:19:22,920 --> 00:19:28,590
>> Vi använde inte steget, men vi gjorde inte
nödvändigtvis för detta fall.

420
00:19:28,590 --> 00:19:32,150
Men vi skulle kunna använda den i lite senare
på idag om vi felsökning, för

421
00:19:32,150 --> 00:19:36,500
exempel binär sökning när binära
Sök heter i ett separat

422
00:19:36,500 --> 00:19:38,200
funktion, men det finns
något fel med det.

423
00:19:38,200 --> 00:19:40,440
Vi kommer att vilja kliva in
samtalet till binär sökning och

424
00:19:40,440 --> 00:19:41,840
faktiskt felsöka det.

425
00:19:41,840 --> 00:19:45,130
Lista vi använde inte heller eftersom vi hade
en bra känsla för vår kod, men om jag

426
00:19:45,130 --> 00:19:48,420
ville få en känsla för vilken kod jag
var runt, jag kunde bara använda listan.

427
00:19:48,420 --> 00:19:50,310
>> Skriv att vi använt, info lokalbefolkningen som vi använt.

428
00:19:50,310 --> 00:19:53,260
Fortsätt att vi inte behöver använda i detta
fall, varken vi behöver använda

429
00:19:53,260 --> 00:19:55,060
inaktivera, men vi gjorde användning sluta.

430
00:19:55,060 --> 00:19:57,850
Återigen, dessa 10 kommandon,
öva på dem.

431
00:19:57,850 --> 00:20:00,770
Om du förstår dessa 10 kommandon,
du bör fastställas för felsökning alla

432
00:20:00,770 --> 00:20:02,525
utfärda med GDB.

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

434
00:20:05,230 --> 00:20:08,420
>> Så vi är på väg att gå på, igen, till
springande punkten i avsnitt idag, att gå över

435
00:20:08,420 --> 00:20:09,720
dessa sortering och sökning
algoritmer.

436
00:20:09,720 --> 00:20:14,075
Innan vi gör det, återigen, några frågor,
kommentarer, oro för GDB?

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

438
00:20:16,750 --> 00:20:20,960
Så är alla kommer att använda
GDB stället printf?

439
00:20:20,960 --> 00:20:24,550
Så alla, för all framtid skull,
alla nickar huvudet rätt

440
00:20:24,550 --> 00:20:27,400
nu, så jag kommer att se dig på kontorstid
och alla TF kommer att se dig och

441
00:20:27,400 --> 00:20:29,460
de kommer att säga, visa mig hur man använder
GDB, och du kommer att kunna

442
00:20:29,460 --> 00:20:31,240
för att visa dem, eller hur?

443
00:20:31,240 --> 00:20:31,760
Typ av?

444
00:20:31,760 --> 00:20:32,640
Kanske förhoppningsvis.

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

446
00:20:33,670 --> 00:20:35,790
>> Så vi kommer att flytta in
sortering och sökning.

447
00:20:35,790 --> 00:20:40,710
Du ser jag har en lista som redan sorterade
för oss, men det kommer inte

448
00:20:40,710 --> 00:20:42,220
vara fallet alltid.

449
00:20:42,220 --> 00:20:49,170
Så i den problembild specifikation för
problem set tre, du har shorts

450
00:20:49,170 --> 00:20:51,410
att du kan titta på, och det faktiskt
ber dig att titta på dessa shorts.

451
00:20:51,410 --> 00:20:55,090
Även i föreläsning i förra veckan, gick vi över
en hel del av dessa algoritmer, så jag är

452
00:20:55,090 --> 00:20:59,150
inte kommer att tillbringa tid i klassen går
över dessa algoritmer igen eller ritning

453
00:20:59,150 --> 00:21:01,130
bilder för hur dessa
algoritmer fungerar.

454
00:21:01,130 --> 00:21:04,030
Återigen, den informationen kan du re-watch
föreläsning, eller att information

455
00:21:04,030 --> 00:21:08,570
fångas utomordentligt på shortsen
för dessa sökningar, alla

456
00:21:08,570 --> 00:21:10,920
som finns på cs50.net.

457
00:21:10,920 --> 00:21:14,200
>> Så istället, vad vi ska
göra är att skriva dessa program.

458
00:21:14,200 --> 00:21:18,190
Vi har en känsla, en mental modell, av hur
de arbetar, och så vad vi ska

459
00:21:18,190 --> 00:21:20,210
göra är att koda dem på riktigt.

460
00:21:20,210 --> 00:21:23,430
Vi ska vända den mentala modell,
den bilden, om man så vill, i

461
00:21:23,430 --> 00:21:24,960
faktiska koden.

462
00:21:24,960 --> 00:21:28,460
Och om du var lite förvirrad eller
dimmig på den mentala modell, jag helt

463
00:21:28,460 --> 00:21:28,770
förstå.

464
00:21:28,770 --> 00:21:30,540
>> Vi ska inte faktiskt kommer att
hoppa till kod direkt.

465
00:21:30,540 --> 00:21:36,030
Så medan denna prompt i detta bildspel frågar
du att koda binär sökning, och

466
00:21:36,030 --> 00:21:39,470
faktiskt, en iterativ version av
binär sökning, det första jag

467
00:21:39,470 --> 00:21:42,370
verkligen vill att du ska göra är att
skriva några pseudokod.

468
00:21:42,370 --> 00:21:47,020
Så du har denna mentala modell
om hur binär sökning fungerar.

469
00:21:47,020 --> 00:21:50,060
Ta ut ett papper om du har
en lätt tillgänglig, eller öppna upp en

470
00:21:50,060 --> 00:21:52,520
textredigerare, och jag skulle vilja
alla att skriva.

471
00:21:52,520 --> 00:21:57,470
Ta fyra minuter att skriva
pseudokod för binär sökning.

472
00:21:57,470 --> 00:21:58,990
>> Återigen, tänk på det mentala modell.

473
00:21:58,990 --> 00:22:01,980
Jag ska komma runt om du har frågor
och vi kan dra bilden ut.

474
00:22:01,980 --> 00:22:06,220
Men först, innan vi börjar programmera,
Jag skulle vilja skriva

475
00:22:06,220 --> 00:22:09,920
pseudokod för binär sökning så när vi
dyka in, har vi några riktning som

476
00:22:09,920 --> 00:22:12,110
där vi ska gå.

477
00:22:12,110 --> 00:22:15,330
>> STUDENT: Kan vi anta den rad av
värden som vi får är redan sorterade?

478
00:22:15,330 --> 00:22:17,960
>> JASON Hirschhorn: Så för binär sökning
till arbete - utmärkt fråga - du

479
00:22:17,960 --> 00:22:20,970
måste ta i en sorterad
matris med värden.

480
00:22:20,970 --> 00:22:22,290
Så antar att det kommer att fungera.

481
00:22:22,290 --> 00:22:23,480
Vi ska gå tillbaka till den här bilden.

482
00:22:23,480 --> 00:22:27,220
Du ser i lila funktionen
deklaration är bool binary_search int

483
00:22:27,220 --> 00:22:29,230
värde, int-värden, int n.

484
00:22:29,230 --> 00:22:32,910
Detta bör ser bekant om du har
redan närmade sig eller fått din

485
00:22:32,910 --> 00:22:34,580
händer smutsiga med problemet set.

486
00:22:34,580 --> 00:22:35,910
>> Men det är funktionsdeklarationen.

487
00:22:35,910 --> 00:22:39,080
Återigen, inte ska behöva oroa sig för
så mycket just nu.

488
00:22:39,080 --> 00:22:43,660
Vad jag verkligen vill att du ska göra är att ta
fyra minuter till pseudo binär

489
00:22:43,660 --> 00:22:46,380
söka, och sedan går vi
över den som en grupp.

490
00:22:46,380 --> 00:22:47,500
Och jag kommer att komma runt.

491
00:22:47,500 --> 00:22:49,590
Om du har frågor är du välkommen
fri att räcka upp handen.

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

493
00:25:07,110 --> 00:25:09,680
>> Varför inte ta två minuter
att avsluta den pseudo?

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

495
00:25:13,690 --> 00:25:15,820
Jag vet att detta kan verka löjligt att
Vi spenderar så mycket tid på

496
00:25:15,820 --> 00:25:20,350
något som inte ens egentligen i
C, men framför allt för dessa mer

497
00:25:20,350 --> 00:25:24,030
utmanande algoritmer och problem
uppsättningar som vi måste ta reda på,

498
00:25:24,030 --> 00:25:27,210
med början i pseudokod inte oroa
om syntaxen, bara behöva oroa

499
00:25:27,210 --> 00:25:29,150
logiken, är otroligt bra.

500
00:25:29,150 --> 00:25:32,720
Och på det sättet, du är inte lösa två
otroligt svåra problem på en gång.

501
00:25:32,720 --> 00:25:35,390
Du ska bara fokusera på logiken, och
då du flyttar in i syntaxen.

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
Låt oss börja gå igenom
pseudokoden.

505
00:26:03,680 --> 00:26:05,380
Jag har skrivit upp här, binär
sökning pseudokod.

506
00:26:05,380 --> 00:26:07,360
Vi kommer att skriva detta på
ombord tillsammans.

507
00:26:07,360 --> 00:26:10,040
Eller ska jag skriva det och du kommer att ge
mig uppmaning jag behöver.

508
00:26:10,040 --> 00:26:15,010
Så kan någon ge mig den första
raden i pseudokoden som du

509
00:26:15,010 --> 00:26:18,350
skrev för binär sökning?

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

511
00:26:20,258 --> 00:26:22,698
>> STUDENT: Medan längden på
listan är större än noll.

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

513
00:26:26,114 --> 00:26:34,880
>> JASON Hirschhorn: Medan längd
på listan är större än noll.

514
00:26:34,880 --> 00:26:38,810
Och återigen ser vi några C-ser
syntaktiska saker på här.

515
00:26:38,810 --> 00:26:41,550
Men det mesta av detta är på engelska.

516
00:26:41,550 --> 00:26:43,980
Var det någon som har någon linje de sätter
innan detta i sin pseudo-kod?

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

518
00:26:47,280 --> 00:26:50,210
>> STUDENT: Få en array
av sorterade siffror.

519
00:26:50,210 --> 00:26:53,600
>> JASON Hirschhorn: Du skrev "få en
matris med sorterade siffror. "Per den

520
00:26:53,600 --> 00:26:56,140
funktionsdeklarationen, kommer vi att passera
en matris av sorterat antal.

521
00:26:56,140 --> 00:26:57,280
>> STUDENTEN [OHÖRBAR].

522
00:26:57,280 --> 00:26:59,030
>> JASON Hirschhorn: Så
Vi kommer att ha det.

523
00:26:59,030 --> 00:27:01,820
Men ja, om vi inte hade det, vi
skulle behöva sortera vårt utbud av

524
00:27:01,820 --> 00:27:04,850
siffror, eftersom binär sökning
bara fungerar på sorterade arrayer.

525
00:27:04,850 --> 00:27:11,300
Så medan längden på listan är lika med noll, jag är
ska sätta i några klammerparenteser

526
00:27:11,300 --> 00:27:15,420
så att det ser lite mer ut som
C. Men samtidigt verkar för att kartlägga på en

527
00:27:15,420 --> 00:27:19,550
while-slinga, så inne i denna stund
loop vad behöver vi för att

528
00:27:19,550 --> 00:27:22,000
göra för binär sökning?

529
00:27:22,000 --> 00:27:25,530
>> Någon annan som inte har gett mig en
svara på ännu men som skrev det här?

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

531
00:27:31,750 --> 00:27:33,320
>> STUDENT: Gå till mitten av listan.

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

533
00:27:33,980 --> 00:27:35,230
Gå till mitten av listan.

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

535
00:27:43,290 --> 00:27:45,530
Och följdfrågan, vad
gör vi när vi är på

536
00:27:45,530 --> 00:27:46,870
mitten av listan?

537
00:27:46,870 --> 00:27:49,310
>> STUDENT: Gör en kontroll om det är
det nummer du letar efter.

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

539
00:27:50,120 --> 00:28:05,500
Gå i mitten av listan och kontrollera
om vårt värde är där -

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

541
00:28:06,515 --> 00:28:10,460
Var det någon som har något annat
som var annorlunda än det här?

542
00:28:10,460 --> 00:28:11,210
Det är precis rätt.

543
00:28:11,210 --> 00:28:13,800
>> Det första vi gör i binär sökning
är att gå till mitten av listan och

544
00:28:13,800 --> 00:28:15,870
kontrollera om vårt värde är där.

545
00:28:15,870 --> 00:28:19,682
Så jag antar att om vårt värde är
där, vad gör vi?

546
00:28:19,682 --> 00:28:21,610
>> STUDENT: Vi återvänder noll [OHÖRBAR].

547
00:28:21,610 --> 00:28:23,400
>> JASON Hirschhorn: Ja, om vår
värde är det, fann vi det.

548
00:28:23,400 --> 00:28:27,950
Så vi kan säga något sätt, men detta
Funktionen är definierad, vi talar om för användaren

549
00:28:27,950 --> 00:28:28,520
vi fann det.

550
00:28:28,520 --> 00:28:30,950
Om det inte finns där, men det är
där det blir knepigt.

551
00:28:30,950 --> 00:28:35,120
Så om det inte finns där, någon annan som
arbetade med binär sökning eller

552
00:28:35,120 --> 00:28:36,830
har en idé nu, vad gör vi?

553
00:28:36,830 --> 00:28:37,830
>> STUDENT: Fråga.

554
00:28:37,830 --> 00:28:38,100
>> JASON Hirschhorn: Ja?

555
00:28:38,100 --> 00:28:39,920
>> STUDENT: Är arrayen redan sorterade?

556
00:28:39,920 --> 00:28:42,200
>> JASON Hirschhorn: Ja, vi antar
matrisen är redan sorterade.

557
00:28:42,200 --> 00:28:46,480
>> STUDENT: Så då måste man kontrollera om
det värde som du ser är större än

558
00:28:46,480 --> 00:28:51,745
det värde som du vill, kan du flytta
till mitten av den andra halvan.

559
00:28:51,745 --> 00:28:54,110
>> JASON Hirschhorn: Så om mitten av
listan är större än vad vi är

560
00:28:54,110 --> 00:28:57,440
söker, då vet vi vad?

561
00:28:57,440 --> 00:28:58,320
Vi rör oss där?

562
00:28:58,320 --> 00:29:01,400
>> STUDENT: Du vill flytta till
den halva av listan med

563
00:29:01,400 --> 00:29:02,780
tal lägre än så.

564
00:29:02,780 --> 00:29:04,460
>> JASON Hirschhorn: Så vi ska
kalla det vänster.

565
00:29:04,460 --> 00:29:15,435
Så om mitten är större, kan vi söka
den vänstra halvan av listan.

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

567
00:29:20,620 --> 00:29:22,980
Och sedan genom sökningen, vilken
menar jag med sökandet?

568
00:29:22,980 --> 00:29:24,010
>> STUDENTEN [OHÖRBAR].

569
00:29:24,010 --> 00:29:24,410
>> JASON Hirschhorn: Vi går till mitten.

570
00:29:24,410 --> 00:29:25,740
Vi upprepar faktiskt denna sak.

571
00:29:25,740 --> 00:29:29,210
Vi går tillbaka genom vår while-slinga.

572
00:29:29,210 --> 00:29:31,480
Jag ska ge er den sista -

573
00:29:31,480 --> 00:29:39,047
annars, om det är mitt mindre än vad
vi gör, vad gör vi här?

574
00:29:39,047 --> 00:29:40,360
>> STUDENT: Gå till höger.

575
00:29:40,360 --> 00:29:41,610
>> JASON Hirschhorn: Sök rätt.

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

577
00:29:47,440 --> 00:29:51,710
Det ser bra ut, men det någon som har
något som vi kanske saknas eller

578
00:29:51,710 --> 00:29:53,200
något annat som du sätter
i pseudo-kod?

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

580
00:29:57,080 --> 00:29:58,410
Så det här är vad vi har hittills.

581
00:29:58,410 --> 00:30:00,960
Även om längden av listan är större
än noll, kommer vi att gå

582
00:30:00,960 --> 00:30:03,220
till mitten av listan och
kontrollera om vårt värde är där.

583
00:30:03,220 --> 00:30:06,970
>> Om mitten är större, kommer vi att
söka vänster, annars om mitten är

584
00:30:06,970 --> 00:30:09,230
mindre, ska vi söka rätt.

585
00:30:09,230 --> 00:30:14,430
Så vi har alla haft viss erfarenhet av
ord vi använder i datavetenskap

586
00:30:14,430 --> 00:30:15,550
och de verktyg vi har.

587
00:30:15,550 --> 00:30:18,300
Men du kommer redan att märka att vi var
tala engelska, men vi hittade en

588
00:30:18,300 --> 00:30:24,790
massa saker som verkade för att kartlägga den till
verktyg som vi har i vår kodning verktygslåda.

589
00:30:24,790 --> 00:30:27,210
Så höger utanför bat, vi är inte
kommer att faktiskt koda ännu.

590
00:30:27,210 --> 00:30:33,300
>> Vad är det vi ser här på engelska som kartor
på att saker och ting kan vi skriva i C?

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

592
00:30:34,560 --> 00:30:35,320
>> JASON Hirschhorn: Medan.

593
00:30:35,320 --> 00:30:40,610
Så denna stund här
kartor på vad?

594
00:30:40,610 --> 00:30:42,630
>> STUDENT: En while-slinga.

595
00:30:42,630 --> 00:30:43,200
>> JASON Hirschhorn: En while-slinga?

596
00:30:43,200 --> 00:30:44,540
Eller förmodligen mer allmänt en slinga.

597
00:30:44,540 --> 00:30:46,260
Vi vill göra något om och om igen.

598
00:30:46,260 --> 00:30:49,050
Så vi kommer att koda en loop.

599
00:30:49,050 --> 00:30:51,640
Och vi redan vet, för vi har gjort
detta ett par gånger och vi

600
00:30:51,640 --> 00:30:54,180
har gott om exempel där ute,
hur man faktiskt skriver

601
00:30:54,180 --> 00:30:55,310
detta index för en slinga.

602
00:30:55,310 --> 00:30:56,160
Så det borde vara ganska lätt.

603
00:30:56,160 --> 00:30:58,070
Vi borde kunna få det
började ganska snabbt.

604
00:30:58,070 --> 00:31:01,830
>> Vad ser vi här?

605
00:31:01,830 --> 00:31:06,820
Vilka andra strukturer syntaxer, saker
som vi känner till i C, gör vi

606
00:31:06,820 --> 00:31:09,790
redan har en känsla utifrån
bort av de ord vi använt?

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

608
00:31:10,830 --> 00:31:11,360
[OHÖRBAR]

609
00:31:11,360 --> 00:31:12,990
bara skojar.

610
00:31:12,990 --> 00:31:13,540
Anna, gå vidare.

611
00:31:13,540 --> 00:31:14,530
>> STUDENT: Om och annat.

612
00:31:14,530 --> 00:31:16,260
>> JASON Hirschhorn: Om och
annat - här.

613
00:31:16,260 --> 00:31:18,840
Så vad gör de se ut?

614
00:31:18,840 --> 00:31:20,420
>> STUDENT: En om annat uttalande.

615
00:31:20,420 --> 00:31:21,560
>> JASON Hirschhorn: Ja,
förhållanden, eller hur?

616
00:31:21,560 --> 00:31:24,650
Så vi måste antagligen
skriva några villkor.

617
00:31:24,650 --> 00:31:31,185
Och återigen, men kanske förvirrande i
första, vi har i allmänhet en känsla nu

618
00:31:31,185 --> 00:31:34,010
om hur man skriver villkor och
syntaxen för villkor.

619
00:31:34,010 --> 00:31:36,850
Och om vi inte gör det, vi ser bara upp
syntax för förhållanden, klippa och klistra

620
00:31:36,850 --> 00:31:39,950
att, eftersom vi vet att vi
behöver en förutsättning för detta.

621
00:31:39,950 --> 00:31:44,910
Alla andra saker som vi ser att kartan på
saker vi kan behöva göra i C?

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

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

624
00:31:48,960 --> 00:31:50,370
>> STUDENT: Det kan vara självklart,
genom att bara kolla om en

625
00:31:50,370 --> 00:31:51,990
värde är lika med något.

626
00:31:51,990 --> 00:31:54,578
>> JASON Hirschhorn: Så hur ska vi kontrollera
och - så gå till mitten av listan

627
00:31:54,578 --> 00:31:55,610
och kolla om vårt värde är det?

628
00:31:55,610 --> 00:31:56,570
Hur ska vi göra det i C?

629
00:31:56,570 --> 00:31:58,450
Vad är syntaxen för det?

630
00:31:58,450 --> 00:31:59,235
>> STUDENT: Lika, lika.

631
00:31:59,235 --> 00:32:00,650
>> JASON Hirschhorn: Lika, lika.

632
00:32:00,650 --> 00:32:03,540
Så denna kontroll är förmodligen kommer
att vara ett likhets, lika.

633
00:32:03,540 --> 00:32:04,510
Så vi vet att vi behöver att någonstans.

634
00:32:04,510 --> 00:32:07,510
Och faktiskt, bara att skriva det,
Vi ser dessa andra saker.

635
00:32:07,510 --> 00:32:11,400
Vi kommer att behöva göra några
jämförelseoperatorer in där -

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

637
00:32:12,010 --> 00:32:14,980
Så det faktiskt ser ut, med och
stora, har vi inte skrivit en

638
00:32:14,980 --> 00:32:16,390
ord av C-kod än.

639
00:32:16,390 --> 00:32:20,610
Men vi fick den mentala modellen ner
via föreläsningar och dessa shorts.

640
00:32:20,610 --> 00:32:22,350
>> Vi skrev pseudo-kod som en grupp.

641
00:32:22,350 --> 00:32:27,110
Och redan har vi 80%, om inte
90% av vad vi behöver göra.

642
00:32:27,110 --> 00:32:28,550
Nu behöver vi bara att koda
den, vilket återigen är en

643
00:32:28,550 --> 00:32:30,110
icke-trivialt problem att lösa.

644
00:32:30,110 --> 00:32:31,890
Men åtminstone vi är fast på logiken.

645
00:32:31,890 --> 00:32:38,040
Åtminstone nu när vi går till kontorstid,
Jag kan säga att jag vet vad jag behöver

646
00:32:38,040 --> 00:32:40,160
att göra, men kan du påminna
mig om syntaxen?

647
00:32:40,160 --> 00:32:42,940
Eller även om kontorstid är trångt, du
kan Google för syntaxen, snarare

648
00:32:42,940 --> 00:32:45,040
än att fastna på logiken.

649
00:32:45,040 --> 00:32:48,570
>> Och återigen, snarare än att försöka lösa
logiken och syntaxproblem alla

650
00:32:48,570 --> 00:32:51,900
på en gång, är det ofta mycket bättre att
bryta dessa två svåra problem ut i

651
00:32:51,900 --> 00:32:58,280
två mer hanterbara och kära och göra det
pseudokod först och sedan koden i C.

652
00:32:58,280 --> 00:33:00,620
Så låt oss se vad jag gjorde för
pseudo-kod i förväg.

653
00:33:00,620 --> 00:33:04,060
>> Även om längden av listan är större
än noll, titta på mitten

654
00:33:04,060 --> 00:33:05,090
i listan.

655
00:33:05,090 --> 00:33:09,610
Om antalet hittade tillbaka sant, annars
om antalet högre, söka vänster.

656
00:33:09,610 --> 00:33:13,200
Else om antalet är lägre, sök
rätt, returnera false.

657
00:33:13,200 --> 00:33:18,710
Så det ser nästan identiska om inte
nästan identisk med vad vi skrivit.

658
00:33:18,710 --> 00:33:23,030
Faktiskt, Tom, det du sa först,
bryta mitt i listan och om

659
00:33:23,030 --> 00:33:24,880
nummer hittas i två rapporter
är faktiskt vad jag gjorde.

660
00:33:24,880 --> 00:33:25,507
>> Jag kombinerade dem där.

661
00:33:25,507 --> 00:33:27,100
Jag borde ha lyssnat på
du första gången.

662
00:33:27,100 --> 00:33:30,640
Så det är den pseudo-kod som vi har.

663
00:33:30,640 --> 00:33:35,060
Om du vill nu, sorry, gå
tillbaka till vårt ursprungliga problem.

664
00:33:35,060 --> 00:33:37,780
Låt oss kod binary.c.

665
00:33:37,780 --> 00:33:40,870
Så genomföra en iterativ version av
binär sökning med hjälp av följande

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

667
00:33:42,420 --> 00:33:44,550
>> Och du behöver inte kopiera
ner riktigt än.

668
00:33:44,550 --> 00:33:49,470
Jag faktiskt går att öppna
upp just här binary.c.

669
00:33:49,470 --> 00:33:52,880
Så det finns funktionsdeklarationen
i mitten av skärmen.

670
00:33:52,880 --> 00:33:57,570
Och så ser jag tog pseudo-kod
från på mina sidor, men nästan identiska

671
00:33:57,570 --> 00:33:59,740
vad vi skrev, och
sätta det i för dig.

672
00:33:59,740 --> 00:34:06,010
Så nu, låt oss ta fem minuter
att koda denna funktion.

673
00:34:06,010 --> 00:34:08,199
>> Och igen, om du har några frågor,
upp handen, låt mig veta, jag ska

674
00:34:08,199 --> 00:34:08,710
komma runt.

675
00:34:08,710 --> 00:34:09,800
>> STUDENTEN [OHÖRBAR].

676
00:34:09,800 --> 00:34:12,380
>> JASON Hirschhorn: Så jag tog det binära
Sök definition på

677
00:34:12,380 --> 00:34:14,429
överst, på linje 12.

678
00:34:14,429 --> 00:34:16,429
Det är vad jag fått för mina slide.

679
00:34:16,429 --> 00:34:20,940
Och sedan allt detta pseudo-kod jag bara
kopiera och klistras från bilden,

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

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

682
00:35:22,830 --> 00:35:26,786
Jag är fortfarande inte höra [OHÖRBAR].

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

684
00:37:13,010 --> 00:37:15,820
>> Så om du är klar med din
genomförande, jag vill kolla upp det.

685
00:37:15,820 --> 00:37:19,410
Jag mailade dig helpers.h filen
tidigare i denna klass.

686
00:37:19,410 --> 00:37:22,360
Och det kommer att finnas tillgängliga på nätet också
för nedladdning för personer som tittar

687
00:37:22,360 --> 00:37:24,750
detta avsnitt tiden fördröjs.

688
00:37:24,750 --> 00:37:29,350
Och jag bara använt den generiska fördelningen
kod från pset3.

689
00:37:29,350 --> 00:37:34,590
Så jag tog find.C, använda min helpers.h fil
snarare än den helpers.h fil

690
00:37:34,590 --> 00:37:36,280
som har gett i distributionen kod.

691
00:37:36,280 --> 00:37:39,310
>> Och jag var tvungen att göra en annan förändring i
find.C snarare än att kräva bara helt enkelt

692
00:37:39,310 --> 00:37:42,770
sök, ring binary_search.

693
00:37:42,770 --> 00:37:49,080
Så om du vill testa din kod,
vet att det är hur man gör det.

694
00:37:49,080 --> 00:37:52,530
Faktum är att när vi ska köra den här koden
just nu, jag gjorde bara en kopia av

695
00:37:52,530 --> 00:37:59,820
min pset3 katalog, återigen, bytte ut
hjälpare filer och sedan gjort att

696
00:37:59,820 --> 00:38:04,695
förändras i find.C ringa binary_search
snarare än att bara söka.

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

698
00:40:08,620 --> 00:40:09,120
>> JASON Hirschhorn: Ja.

699
00:40:09,120 --> 00:40:11,258
Har du frågor?

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

701
00:40:12,150 --> 00:40:12,600
>> JASON Hirschhorn: Inga bekymmer.

702
00:40:12,600 --> 00:40:13,370
Nåväl, låt oss komma igång.

703
00:40:13,370 --> 00:40:15,090
Vi kommer att koda detta som en grupp.

704
00:40:15,090 --> 00:40:16,050
En andra anmärkning.

705
00:40:16,050 --> 00:40:20,600
Återigen, detta är, kan enkelt bytas ut mot
in för Problem Set Tre.

706
00:40:20,600 --> 00:40:25,530
Jag har min helpers.h fil som, snarare
än helpers.h vi gett,

707
00:40:25,530 --> 00:40:28,560
förklarar binär sökning, bubbla
sortera och val av sort.

708
00:40:28,560 --> 00:40:37,400
Och i find.c märker du på linjen,
vad är det, linje 68, kallar vi binär

709
00:40:37,400 --> 00:40:39,160
sök snarare än sökning.

710
00:40:39,160 --> 00:40:42,930
Så återigen, den kod som är tillgänglig
nätet eller den kod som du är

711
00:40:42,930 --> 00:40:46,590
skapar just nu lätt kan bytas
i för p set 3 för att kontrollera det.

712
00:40:46,590 --> 00:40:50,620
>> Men först, låt oss koda binär sökning.

713
00:40:50,620 --> 00:40:53,690
Vår funktion deklaration,
vi tillbaka en bool.

714
00:40:53,690 --> 00:40:55,810
Vi tar ett heltal som kallas värde.

715
00:40:55,810 --> 00:40:59,285
Vi tar en array av heltal kallas
värderingar, och vi tar n vara

716
00:40:59,285 --> 00:41:00,850
storleken på matrisen.

717
00:41:00,850 --> 00:41:05,640
På rad 10, just här, har jag
skarp inkluderar stdbool.h.

718
00:41:05,640 --> 00:41:07,360
Är det någon som vet varför det finns där?

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

720
00:41:12,180 --> 00:41:16,600
Så vad betyder det kodrad göra?

721
00:41:16,600 --> 00:41:19,880
>> STUDENT: Det kan du
använda en typ bool avkastning.

722
00:41:19,880 --> 00:41:20,350
>> JASON Hirschhorn: Exakt.

723
00:41:20,350 --> 00:41:22,300
>> STUDENT: Eller det är ett bibliotek som gör att
att använda en typ bool avkastning.

724
00:41:22,300 --> 00:41:27,590
>> JASON Hirschhorn: Så den kraftiga inkluderar
stdbool.h linje ger mig några

725
00:41:27,590 --> 00:41:31,340
definitioner och förklaringar för saker
att jag får använda i

726
00:41:31,340 --> 00:41:32,400
detta bibliotek.

727
00:41:32,400 --> 00:41:36,570
Så bland de som säger att det finns
denna typ kallas bool, och det kan vara

728
00:41:36,570 --> 00:41:37,750
sant eller falskt.

729
00:41:37,750 --> 00:41:39,010
Så det är vad den linjen gör.

730
00:41:39,010 --> 00:41:41,680
Och om jag inte har den linjen, skulle jag
få i trubbel för att skriva detta

731
00:41:41,680 --> 00:41:43,520
ord här, bool, precis där.

732
00:41:43,520 --> 00:41:44,140
Exakt rätt.

733
00:41:44,140 --> 00:41:46,430
Så jag behöver det i denna kod.

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

735
00:41:47,690 --> 00:41:51,860
Så denna, återigen, är en iterativ
versionen, inte en rekursiv en.

736
00:41:51,860 --> 00:41:53,820
Så låt oss komma igång.

737
00:41:53,820 --> 00:41:56,200
>> Låt oss börja med det första
linje av pseudokod.

738
00:41:56,200 --> 00:41:58,770
Och förhoppningsvis kommer vi -
eller inte förhoppningsvis.

739
00:41:58,770 --> 00:42:00,530
Vi kommer att gå runt i rummet.

740
00:42:00,530 --> 00:42:05,110
Vi går rad för rad, och jag kommer att hjälpa
du räkna ut den linje som vi behöver

741
00:42:05,110 --> 00:42:06,310
att skriva först.

742
00:42:06,310 --> 00:42:10,550
Så medan längden på listan
är större än noll.

743
00:42:10,550 --> 00:42:12,680
Låt oss börja i fronten.

744
00:42:12,680 --> 00:42:15,190
Vilken linje ska jag skriva
Här, i kod?

745
00:42:15,190 --> 00:42:19,470
>> STUDENT: Även parentes
n är större än 0.

746
00:42:19,470 --> 00:42:21,900
>> JASON Hirschhorn: Medan
n är stor än 0.

747
00:42:21,900 --> 00:42:26,550
Så n är storleken på en lista,
och vi kollar om -

748
00:42:26,550 --> 00:42:26,800
>> [inplacering UTTRYCKER]

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

750
00:42:27,660 --> 00:42:29,360
>> STUDENT: Hur vet vi att
n är storleken på listan?

751
00:42:29,360 --> 00:42:29,690
>> JASON Hirschhorn: Förlåt.

752
00:42:29,690 --> 00:42:34,690
Per den pset specifikation, sökandet
och fungerar sorterar du behöver för att skriva,

753
00:42:34,690 --> 00:42:36,230
n är storleken på listan.

754
00:42:36,230 --> 00:42:37,710
Jag glömde att förklara det här.

755
00:42:37,710 --> 00:42:41,310
Men ja. n är storleken på
listan, i det här fallet.

756
00:42:41,310 --> 00:42:44,740
Så medan n är större än 0.

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

758
00:42:45,580 --> 00:42:50,090
Det kan visa sig vara lite problematiskt
Men om det går på.

759
00:42:50,090 --> 00:42:54,510
Eftersom vi kommer att fortsätta att känna till
storleken på listan under hela denna

760
00:42:54,510 --> 00:43:06,640
funktion, men säger att vi börjar
med en samling av fem heltal.

761
00:43:06,640 --> 00:43:08,950
Och vi går igenom och vi har
nu minskat ner det till

762
00:43:08,950 --> 00:43:10,310
en uppsättning av två heltal.

763
00:43:10,310 --> 00:43:12,160
Vilka två heltal är det?

764
00:43:12,160 --> 00:43:15,895
Storleken är 2 nu när vi vill
titta på, men som 2 är det?

765
00:43:15,895 --> 00:43:17,720
Är det vettigt att fråga?

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

767
00:43:18,020 --> 00:43:19,120
Jag frågar igen.

768
00:43:19,120 --> 00:43:26,640
Så vi börjar med denna samling av 5
heltal, och n är lika med 5, eller hur?

769
00:43:26,640 --> 00:43:28,050
Vi kommer att gå igenom här.

770
00:43:28,050 --> 00:43:31,560
Vi ska nog ändra storlek,
rätt, eftersom det går på.

771
00:43:31,560 --> 00:43:32,700
Vilket är vad vi säger att vi vill göra.

772
00:43:32,700 --> 00:43:34,150
Vi vill inte söka
hela saken igen.

773
00:43:34,150 --> 00:43:35,480
Så säger vi ändra det till 2.

774
00:43:35,480 --> 00:43:36,970
Vi tar halva listan som är konstigt.

775
00:43:36,970 --> 00:43:38,800
Så bara plocka 2.

776
00:43:38,800 --> 00:43:40,590
Så nu n är lika med 2.

777
00:43:40,590 --> 00:43:42,780
Jag ber om ursäkt för de fattiga
torra radera markörer.

778
00:43:42,780 --> 00:43:43,080
Rätt?

779
00:43:43,080 --> 00:43:45,670
Och vi söker igenom listan
igen med en lista med storlek 2.

780
00:43:45,670 --> 00:43:48,580
Tja, är vår samling fortfarande av storlek 5.

781
00:43:48,580 --> 00:43:51,920
Vi säger att vi bara vill
Sök 2 fläckar i den.

782
00:43:51,920 --> 00:43:53,590
Så som två fläckar är de?

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

784
00:43:57,640 --> 00:43:58,815
>> Låter det vettigt?

785
00:43:58,815 --> 00:44:00,290
Är de vänster 2 fläckar?

786
00:44:00,290 --> 00:44:01,940
Är de rätt 2 ställen?

787
00:44:01,940 --> 00:44:03,540
Är de de 2 mitt fläckar?

788
00:44:03,540 --> 00:44:06,350
Vi har brutit problemet ner, men vi
faktiskt inte vet vilken del av

789
00:44:06,350 --> 00:44:11,600
problemet vi fortfarande tittar på,
bara genom att ha dessa två variabler.

790
00:44:11,600 --> 00:44:16,450
Så vi behöver lite mer då,
medan n är större än 0.

791
00:44:16,450 --> 00:44:21,410
Vi måste veta var det
n är i våra faktiska array.

792
00:44:21,410 --> 00:44:26,660
>> Så det någon som har en
byta till denna linje?

793
00:44:26,660 --> 00:44:27,970
Merparten av denna linje är
helt rätt.

794
00:44:27,970 --> 00:44:29,170
Finns det ett annat tillägg?

795
00:44:29,170 --> 00:44:32,510
Kan vi byta ut något för n till
gör denna linje lite bättre?

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

797
00:44:32,865 --> 00:44:38,040
>> STUDENT: Kan du initierar en variabel
såsom längd på n som sedan kommer att användas

798
00:44:38,040 --> 00:44:39,600
senare i funktion?

799
00:44:39,600 --> 00:44:42,060
>> JASON Hirschhorn: Så initiera
en variabel längd med n,

800
00:44:42,060 --> 00:44:42,900
och vi använder det senare?

801
00:44:42,900 --> 00:44:47,070
Men då vi uppdaterar bara längd och vi
fortfarande stöter på detta problem, där vi

802
00:44:47,070 --> 00:44:51,180
skära ner längden på vårt problem,
men vi vet aldrig var, faktiskt,

803
00:44:51,180 --> 00:44:52,510
denna längd kartor på.

804
00:44:52,510 --> 00:44:54,790
>> STUDENT: Är inte det kommer att hända
senare när du säger, söka vänster,

805
00:44:54,790 --> 00:44:55,746
Sök rätt?

806
00:44:55,746 --> 00:44:57,640
Du kommer att gå till en annan
område av ditt -

807
00:44:57,640 --> 00:44:59,110
>> JASON Hirschhorn: Vi kommer att gå
till ett område, men hur vet vi

808
00:44:59,110 --> 00:45:01,150
vilket är att gå till?

809
00:45:01,150 --> 00:45:03,800
Om vi ​​bara har matrisen och denna
n, hur vet vi var de ska

810
00:45:03,800 --> 00:45:05,050
gå till i arrayen.

811
00:45:05,050 --> 00:45:05,900
I ryggen, ja?

812
00:45:05,900 --> 00:45:07,507
>> STUDENT: Har du, liksom, en lägre
gräns och en övre gräns variabel eller

813
00:45:07,507 --> 00:45:08,586
något sådant?

814
00:45:08,586 --> 00:45:09,060
>> JASON Hirschhorn: OK.

815
00:45:09,060 --> 00:45:10,780
Så det här är en annan idé.

816
00:45:10,780 --> 00:45:13,490
Snarare än att bara hålla reda på
storlek, vi hålla reda på den nedre och

817
00:45:13,490 --> 00:45:14,770
övre gräns variabel.

818
00:45:14,770 --> 00:45:17,840
Så hur vi beräknar storleken från
en undre gräns och övre gräns?

819
00:45:17,840 --> 00:45:18,520
>> [inplacering UTTRYCKER]

820
00:45:18,520 --> 00:45:19,710
>> JASON Hirschhorn: subtraktion.

821
00:45:19,710 --> 00:45:23,650
Och även att hålla reda på den nedre
bundna och övre gräns för att låta oss veta,

822
00:45:23,650 --> 00:45:26,215
Vi söker dessa två?

823
00:45:26,215 --> 00:45:28,220
Ska vi söka dessa två hit?

824
00:45:28,220 --> 00:45:29,540
Ska vi söka på två mitten?

825
00:45:29,540 --> 00:45:32,810
Förmodligen inte de två mellersta, eftersom
detta i själva verket är binär sökning.

826
00:45:32,810 --> 00:45:37,320
Men nu kommer vi att kunna få den storlek,
utan också gränserna för arrayen.

827
00:45:37,320 --> 00:45:40,020
I huvudsak, om vi har vår jätte
telefonbok, vi slita den på mitten.

828
00:45:40,020 --> 00:45:42,990
Vi vet nu var det mindre
telefonbok är.

829
00:45:42,990 --> 00:45:45,260
Men vi är faktiskt rippning
telefonboken i halv.

830
00:45:45,260 --> 00:45:48,570
Vi behöver fortfarande veta var
nya gränserna för vårt problem är.

831
00:45:48,570 --> 00:45:51,645
Är det någon som har några frågor
om det?

832
00:45:51,645 --> 00:45:52,440
Ja?

833
00:45:52,440 --> 00:45:56,020
>> STUDENT: Skulle det fungera genom att skapa en
variabel, jag, att du sedan bara flytta

834
00:45:56,020 --> 00:46:00,770
position i förhållande till dess
nuvarande position, och längden, n?

835
00:46:00,770 --> 00:46:01,710
>> JASON Hirschhorn: Och vad är jag?

836
00:46:01,710 --> 00:46:04,110
>> STUDENT: Som jag vara som sorts -

837
00:46:04,110 --> 00:46:08,040
Som du vill initiera i för att vara den
mellanposition av matrisen.

838
00:46:08,040 --> 00:46:12,540
Och sedan, om värdet på position i i
mitten av uppsättningen i befunnits

839
00:46:12,540 --> 00:46:17,870
vara lägre än det värde som du behöver, jag nu
blir längden av arrayen, plus

840
00:46:17,870 --> 00:46:19,215
Värdet på I dividerat med två.

841
00:46:19,215 --> 00:46:20,270
Liksom, se, flytta dig i -

842
00:46:20,270 --> 00:46:20,770
>> JASON Hirschhorn: Höger.

843
00:46:20,770 --> 00:46:21,165
>> STUDENT: - upp till -

844
00:46:21,165 --> 00:46:24,010
>> JASON Hirschhorn: Så jag är nästan
positiva som kommer att fungera.

845
00:46:24,010 --> 00:46:26,800
Men poängen är, behöver du två
bitar av information här.

846
00:46:26,800 --> 00:46:30,050
Du kan göra det med början och slut,
eller så kan du göra det med storlek, och sedan

847
00:46:30,050 --> 00:46:31,060
någon markör.

848
00:46:31,060 --> 00:46:32,630
Men du behöver två stycken
av information här.

849
00:46:32,630 --> 00:46:34,160
Du kan inte klara sig med bara en.

850
00:46:34,160 --> 00:46:35,830
Låter det vettigt?

851
00:46:35,830 --> 00:46:39,560
>> Så vi kommer att gå igenom, och
vi kommer att göra [OHÖRBAR]

852
00:46:39,560 --> 00:46:41,330
och skapa några markörer.

853
00:46:41,330 --> 00:46:42,690
Vad gjorde du skriver in din kod?

854
00:46:42,690 --> 00:46:46,190
>> STUDENT: Jag sa bara int bunden
en är lika med 0.

855
00:46:46,190 --> 00:46:47,790
>> JASON Hirschhorn: Låt oss kalla
att int, början.

856
00:46:47,790 --> 00:46:49,140
>> STUDENT: OK.

857
00:46:49,140 --> 00:46:50,590
>> JASON Hirschhorn: Det gör
mer meningsfullt för mig.

858
00:46:50,590 --> 00:46:51,670
Och?

859
00:46:51,670 --> 00:46:54,340
>> STUDENT: Jag sa, jag antar, int slutar.

860
00:46:54,340 --> 00:46:55,870
>> JASON Hirschhorn: int slutar.

861
00:46:55,870 --> 00:46:57,640
>> STUDENT: Jag antar, n minus 1,
eller något liknande.

862
00:46:57,640 --> 00:46:59,100
Liksom, det sista elementet.

863
00:46:59,100 --> 00:47:02,310
>> JASON Hirschhorn: Så du skrev, int
början är lika med 0, semikolon, och int

864
00:47:02,310 --> 00:47:04,320
slut är lika med n minus 1, semikolon.

865
00:47:04,320 --> 00:47:06,850
Så i huvudsak, vad vi gör
Här, 0 den första positionen.

866
00:47:06,850 --> 00:47:09,570
Och som vi vet i matriser, går de inte
upp till n, går de upp till n minus 1.

867
00:47:09,570 --> 00:47:11,110
Så vi har några gränser för vår samling.

868
00:47:11,110 --> 00:47:15,730
Och dessa inledande gränser råkar vara
de ursprungliga gränserna för vårt problem.

869
00:47:15,730 --> 00:47:16,640
OK.

870
00:47:16,640 --> 00:47:19,200
Så det låter bra.

871
00:47:19,200 --> 00:47:22,380
Sen om vi går tillbaka till denna linje, medan
längden av listan är större än 0,

872
00:47:22,380 --> 00:47:24,752
vilken, i stället för N, bör
vi sätter in här?

873
00:47:24,752 --> 00:47:28,820
>> STUDENT: Skriv slutar minus början.

874
00:47:28,820 --> 00:47:34,780
>> JASON Hirschhorn: När slutar minus
början är större än 0?

875
00:47:34,780 --> 00:47:35,480
OK.

876
00:47:35,480 --> 00:47:37,730
Och vi kunde, om vi ville
göra det lite trevligare, vad

877
00:47:37,730 --> 00:47:38,980
annat kunde vi göra?

878
00:47:38,980 --> 00:47:41,650

879
00:47:41,650 --> 00:47:43,412
Om vi ​​ville rensa
denna kod upp lite?

880
00:47:43,412 --> 00:47:46,716

881
00:47:46,716 --> 00:47:48,180
Hur kan vi bli av med 0?

882
00:47:48,180 --> 00:47:51,560

883
00:47:51,560 --> 00:47:52,690
Detta är bara en fråga stil.

884
00:47:52,690 --> 00:47:53,690
Det är rätt just nu.

885
00:47:53,690 --> 00:47:54,870
>> STUDENTEN Ending inte
lika början?

886
00:47:54,870 --> 00:47:55,740
>> JASON Hirschhorn: Vi kan göra vad?

887
00:47:55,740 --> 00:47:56,730
>> [inplacering UTTRYCKER]

888
00:47:56,730 --> 00:47:57,330
>> STUDENTEN Ending är större?

889
00:47:57,330 --> 00:47:57,720
>> JASON Hirschhorn: Ja.

890
00:47:57,720 --> 00:48:01,110
Vi kan bara göra när du slutar
är större än början.

891
00:48:01,110 --> 00:48:03,580
Rätt.

892
00:48:03,580 --> 00:48:06,240
Vi lade början till andra sidan
om det, och vi blev av med 0.

893
00:48:06,240 --> 00:48:08,000
Så det här bara ser en
lite renare.

894
00:48:08,000 --> 00:48:08,990
OK.

895
00:48:08,990 --> 00:48:11,460
Så, medan längden på listan är 0, skrev vi
som är större samtidigt som slutar

896
00:48:11,460 --> 00:48:12,240
än början.

897
00:48:12,240 --> 00:48:19,840
Vi kommer att sätta in vårt behov
klamrar, och sedan det första

898
00:48:19,840 --> 00:48:22,090
vi vill göra är att titta på
dem i en liten lista.

899
00:48:22,090 --> 00:48:22,510
Du?

900
00:48:22,510 --> 00:48:23,320
Kan du ge mig den -

901
00:48:23,320 --> 00:48:26,460
>> STUDENT: Om parentes
värde hakparentes -

902
00:48:26,460 --> 00:48:30,450
>> JASON Hirschhorn: Om parenteser
värde hakparentes.

903
00:48:30,450 --> 00:48:33,210
>> STUDENT: slutar delat med 2.

904
00:48:33,210 --> 00:48:33,952
>> JASON Hirschhorn: Ending?

905
00:48:33,952 --> 00:48:35,280
>> STUDENT: Jag ser ett problem med ditt -

906
00:48:35,280 --> 00:48:35,750
>> JASON Hirschhorn: OK.

907
00:48:35,750 --> 00:48:39,150
Tja, titta på mitten.

908
00:48:39,150 --> 00:48:41,226
Hur vet vi vad mitt är?

909
00:48:41,226 --> 00:48:42,450
Yeah.

910
00:48:42,450 --> 00:48:43,070
Så låt mig ta bort den koden.

911
00:48:43,070 --> 00:48:46,360
Hur vet vi vad mitt är?

912
00:48:46,360 --> 00:48:48,003
I vad som helst, när du har början
och i slutet, hur tycker du att

913
00:48:48,003 --> 00:48:48,876
mitten?

914
00:48:48,876 --> 00:48:49,590
>> STUDENT: Du genomsnitt.

915
00:48:49,590 --> 00:48:51,820
>> STUDENT: Du lägger dem
tillsammans och sedan -

916
00:48:51,820 --> 00:48:53,150
>> JASON Hirschhorn: Lägg dem
tillsammans och sedan?

917
00:48:53,150 --> 00:48:54,090
>> STUDENT: Och du genomsnitt.

918
00:48:54,090 --> 00:48:55,050
Dela det med 2.

919
00:48:55,050 --> 00:48:56,500
>> JASON Hirschhorn: Lägg dem
samman och dividera med 2.

920
00:48:56,500 --> 00:48:59,400
Så int mitten är lika?

921
00:48:59,400 --> 00:49:01,120
Tom, kan du ge den till mig?

922
00:49:01,120 --> 00:49:03,550
>> STUDENT: Början plus slutar -

923
00:49:03,550 --> 00:49:04,950
>> JASON Hirschhorn: Början
plus slutar.

924
00:49:04,950 --> 00:49:06,880
>> STUDENT: Alla, hållare, delat med 2.

925
00:49:06,880 --> 00:49:10,940
>> JASON Hirschhorn: Alla, inom parentes,
dividerad med två.

926
00:49:10,940 --> 00:49:16,300
Så det ger mig mitt
av något, korrigera?

927
00:49:16,300 --> 00:49:18,980
>> STUDENT: Du måste också att runda upp.

928
00:49:18,980 --> 00:49:19,990
>> JASON Hirschhorn: Vad gör du
menar, jag behöver för att runda upp det?

929
00:49:19,990 --> 00:49:20,400
>> [inplacering UTTRYCKER]

930
00:49:20,400 --> 00:49:24,520
>> STUDENT: För om det är en udda
nummer, då är det som om -

931
00:49:24,520 --> 00:49:25,440
>> JASON Hirschhorn: Tja, OK.

932
00:49:25,440 --> 00:49:26,360
Så jag kunde runda upp.

933
00:49:26,360 --> 00:49:33,350
Men om det är ett ojämnt antal, 5, kan jag
tar en bort från mitten.

934
00:49:33,350 --> 00:49:35,665
Eller om det är ett jämnt tal, snarare
det är en bättre fråga.

935
00:49:35,665 --> 00:49:39,600
Om det är 4, har vi bara 4, kan jag ta
den första "mitten", citat, unquote eller

936
00:49:39,600 --> 00:49:41,760
den andra "mitt" en.

937
00:49:41,760 --> 00:49:46,390
Antingen skulle fungera för en binär sökning,
så jag egentligen inte behöver för att runda det.

938
00:49:46,390 --> 00:49:48,640
Men det finns en annan sak som jag
måste titta på den här raden.

939
00:49:48,640 --> 00:49:50,530
Vi kanske inte inser det än,
men vi ska återkomma till det.

940
00:49:50,530 --> 00:49:53,200
Eftersom denna linje faktiskt fortfarande
behöver en annan sak.

941
00:49:53,200 --> 00:49:55,990
>> Men än så länge har vi skrivit
fyra rader kod.

942
00:49:55,990 --> 00:49:58,120
Vi har fått vår början
och slutar markörer.

943
00:49:58,120 --> 00:50:01,320
Vi har vår while-slinga, som kartlägger
den direkt till vår pseudokod.

944
00:50:01,320 --> 00:50:05,790
Vi tittar på mitten som mappar
direkt på vår pseudokod.

945
00:50:05,790 --> 00:50:09,070
Jag skulle säga att detta går till mitten
på listan, denna rad kod.

946
00:50:09,070 --> 00:50:11,560
Och sedan, när vi går till mitten av
listan, nästa sak vi måste göra

947
00:50:11,560 --> 00:50:14,880
är kontrollera om vårt värde är där för
den pseudokod som vi skrev tidigare.

948
00:50:14,880 --> 00:50:17,100
>> Så hur ska vi kontrollera om vårt värde
är vid mitten av listan?

949
00:50:17,100 --> 00:50:17,300
Du.

950
00:50:17,300 --> 00:50:18,511
Varför inte göra det här?

951
00:50:18,511 --> 00:50:23,070
>> STUDENT: Om vårt värde är är
vid mitten är lika med

952
00:50:23,070 --> 00:50:24,592
vad vi än ställer in -

953
00:50:24,592 --> 00:50:26,190
Jag menar lika lika med -

954
00:50:26,190 --> 00:50:26,690
>> JASON Hirschhorn: Det -

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: Jag är inte säker på vad det
variabel vi söker

958
00:50:32,170 --> 00:50:32,850
för även om, är att -

959
00:50:32,850 --> 00:50:33,330
>> [inplacering UTTRYCKER]

960
00:50:33,330 --> 00:50:34,520
>> STUDENTEN [OHÖRBAR].

961
00:50:34,520 --> 00:50:35,060
>> JASON Hirschhorn: Exakt.

962
00:50:35,060 --> 00:50:37,260
Per funktionsdeklarationen,
Vi letar efter ett värde.

963
00:50:37,260 --> 00:50:39,760
Så vi söker efter ett värde
i en matris med värden.

964
00:50:39,760 --> 00:50:41,080
Så du är exakt rätt.

965
00:50:41,080 --> 00:50:45,040
Du kommer att göra, om det öppna föräldra värde fäste
mitten stängd Fästets jämlikar

966
00:50:45,040 --> 00:50:49,930
lika värde, och inuti finns
vad behöver vi göra?

967
00:50:49,930 --> 00:50:51,230
Om vårt värde är där, vad
behöver vi göra?

968
00:50:51,230 --> 00:50:51,420
>> [inplacering UTTRYCKER]

969
00:50:51,420 --> 00:50:52,160
>> STUDENT: Tillbaka noll.

970
00:50:52,160 --> 00:50:53,070
>> JASON Hirschhorn: Returnera sant.

971
00:50:53,070 --> 00:50:54,790
>> STUDENT: Returnera sant.

972
00:50:54,790 --> 00:50:57,856
>> JASON Hirschhorn: Michael,
vad gör denna linje göra?

973
00:50:57,856 --> 00:51:01,105
>> STUDENTEN [OHÖRBAR] programmet har körts
sin gång, och det är över, och

974
00:51:01,105 --> 00:51:01,920
du har vad du behöver göra?

975
00:51:01,920 --> 00:51:03,030
>> JASON Hirschhorn: Programmet eller vad?

976
00:51:03,030 --> 00:51:03,700
I det här fallet?

977
00:51:03,700 --> 00:51:04,210
>> STUDENT: Funktionen.

978
00:51:04,210 --> 00:51:05,170
>> JASON Hirschhorn: Funktionen.

979
00:51:05,170 --> 00:51:08,420
Och så, för att återgå till vad som kallas
den och ge den värdet sant.

980
00:51:08,420 --> 00:51:09,890
Exakt rätt.

981
00:51:09,890 --> 00:51:10,170
Main.

982
00:51:10,170 --> 00:51:12,035
Vad är det för typ retur
av huvud, Michael?

983
00:51:12,035 --> 00:51:16,480

984
00:51:16,480 --> 00:51:17,150
>> STUDENT: int, heltal?

985
00:51:17,150 --> 00:51:18,080
>> JASON Hirschhorn: int, exakt.

986
00:51:18,080 --> 00:51:18,680
Ett heltal.

987
00:51:18,680 --> 00:51:20,980
Det var bara en fråga för att se till
ni har varit på toppen av det.

988
00:51:20,980 --> 00:51:24,250
Vad innebär det oftast tillbaka, om
allting fungerar bra?

989
00:51:24,250 --> 00:51:24,520
>> STUDENT: Noll.

990
00:51:24,520 --> 00:51:24,820
>> JASON Hirschhorn: Zero.

991
00:51:24,820 --> 00:51:25,430
Exakt rätt.

992
00:51:25,430 --> 00:51:28,790
>> STUDENT: Om detta återkommer bara sant,
det finns ingen information som ges

993
00:51:28,790 --> 00:51:30,675
om vad -

994
00:51:30,675 --> 00:51:34,040
Åh, det är bara att säga att det
värde är inuti matrisen.

995
00:51:34,040 --> 00:51:35,350
>> JASON Hirschhorn: Exakt.

996
00:51:35,350 --> 00:51:38,080
Detta program är inte att ge information
om var exakt värde är.

997
00:51:38,080 --> 00:51:41,850
Det är bara att säga, ja, vi hittade
det, eller nej, det gjorde vi inte det.

998
00:51:41,850 --> 00:51:42,990
Så om antalet hittas, return true.

999
00:51:42,990 --> 00:51:45,500
Jo, faktiskt vi bara gjorde det riktigt
snabbt med att en rad kod.

1000
00:51:45,500 --> 00:51:47,500
Så jag ska flytta den linjen av pseudokod.

1001
00:51:47,500 --> 00:51:50,045
>> STUDENT: Inte vi behöver
att ändra arrayen?

1002
00:51:50,045 --> 00:51:52,830
Det bör vara värden, inte värde, eller hur?

1003
00:51:52,830 --> 00:51:53,430
>> JASON Hirschhorn: Förlåt.

1004
00:51:53,430 --> 00:51:54,010
Tack.

1005
00:51:54,010 --> 00:51:54,800
>> STUDENT: Ja.

1006
00:51:54,800 --> 00:51:55,850
>> JASON Hirschhorn: Denna rad
bör vara värden.

1007
00:51:55,850 --> 00:51:57,150
Exakt rätt.

1008
00:51:57,150 --> 00:51:57,920
OK.

1009
00:51:57,920 --> 00:51:59,170
Så vi har tittat på mitt lista.

1010
00:51:59,170 --> 00:52:00,790
Om antalet hittade avkastning sant.

1011
00:52:00,790 --> 00:52:04,470
Fortsätter med vår pseudokod, om
mitten är större, sök kvar.

1012
00:52:04,470 --> 00:52:09,640
Så jag hade i här, om antalet
högre, sök kvar.

1013
00:52:09,640 --> 00:52:12,700

1014
00:52:12,700 --> 00:52:14,462
Konstantin, kan du ge
mig denna kodrad?

1015
00:52:14,462 --> 00:52:17,240

1016
00:52:17,240 --> 00:52:23,520
>> STUDENT: Om värdet på mitten -

1017
00:52:23,520 --> 00:52:24,890
>> JASON Hirschhorn: Så om värde -

1018
00:52:24,890 --> 00:52:28,890
om öppen paren värderar fäste
mitten nära fäste -

1019
00:52:28,890 --> 00:52:31,500
>> STUDENT: Är mindre än värdet?

1020
00:52:31,500 --> 00:52:32,760
>> JASON Hirschhorn: Är mindre än.

1021
00:52:32,760 --> 00:52:33,800
>> STUDENT: Mindre än värdet.

1022
00:52:33,800 --> 00:52:34,060
>> JASON Hirschhorn: Värde.

1023
00:52:34,060 --> 00:52:35,310
Jo, faktiskt, vill du
kontrollera om numret -

1024
00:52:35,310 --> 00:52:38,310

1025
00:52:38,310 --> 00:52:38,490
Ursäkta.

1026
00:52:38,490 --> 00:52:39,140
Det är lite förvirrande.

1027
00:52:39,140 --> 00:52:43,920
Men annars om antalet i
mitt i listan är större.

1028
00:52:43,920 --> 00:52:45,170
>> STUDENT: Åh, OK.

1029
00:52:45,170 --> 00:52:49,800

1030
00:52:49,800 --> 00:52:50,410
>> JASON Hirschhorn: Jag ska ändra på det.

1031
00:52:50,410 --> 00:52:55,060
Annars om mitten är högre, vi
vill söka vänster, OK?

1032
00:52:55,060 --> 00:52:57,310
Och vad gör vi inne
detta om tillstånd?

1033
00:52:57,310 --> 00:53:03,660

1034
00:53:03,660 --> 00:53:07,510
>> STUDENT: Kan jag göra en liten förändring till
tillståndet, ändra det till annars om?

1035
00:53:07,510 --> 00:53:08,380
>> JASON Hirschhorn: Else om?

1036
00:53:08,380 --> 00:53:09,270
OK.

1037
00:53:09,270 --> 00:53:12,840
Så här koden kommer att utföra
ungefär samma.

1038
00:53:12,840 --> 00:53:18,620
Men det fina med att använda om, annars
om, annars om eller om det, annars om, annars

1039
00:53:18,620 --> 00:53:22,320
innebär att endast en av dem kommer att
kontrolleras, inte alla tre av dem,

1040
00:53:22,320 --> 00:53:23,290
potentiellt.

1041
00:53:23,290 --> 00:53:25,530
Och det gör det lite
trevligare på den dator som är

1042
00:53:25,530 --> 00:53:26,670
köra ditt program.

1043
00:53:26,670 --> 00:53:27,620
>> Så [? Konstantin,?]

1044
00:53:27,620 --> 00:53:31,330
Vi är inne i den här linjen, annars om värderingar,
fäste mitten nära fästet

1045
00:53:31,330 --> 00:53:32,260
är större än värdet.

1046
00:53:32,260 --> 00:53:33,150
Vad behöver vi göra?

1047
00:53:33,150 --> 00:53:33,970
Vi måste söka vänster.

1048
00:53:33,970 --> 00:53:35,220
Hur gör vi det?

1049
00:53:35,220 --> 00:53:46,960

1050
00:53:46,960 --> 00:53:48,720
Jag ska ge dig en start.

1051
00:53:48,720 --> 00:53:52,210
>> Vi har dessa två saker som kallas
börjar och slutar.

1052
00:53:52,210 --> 00:53:57,340
Så vad som behöver hända
till början?

1053
00:53:57,340 --> 00:53:59,640
Om du vill söka till vänster om
lista, får vi vår nuvarande början.

1054
00:53:59,640 --> 00:54:01,080
Vad behöver vi göra det?

1055
00:54:01,080 --> 00:54:04,220
>> STUDENT: Vi sätter början
till mitten plus 1.

1056
00:54:04,220 --> 00:54:05,120
>> JASON Hirschhorn: Så om vi är
söka på vänster?

1057
00:54:05,120 --> 00:54:06,250
>> STUDENT: Förlåt, mitt minus -

1058
00:54:06,250 --> 00:54:11,310
så ändelsen skulle vara mitt
minus 1 och början -

1059
00:54:11,310 --> 00:54:12,450
>> JASON Hirschhorn: Och vad
händer med början?

1060
00:54:12,450 --> 00:54:13,210
>> STUDENT: Det förblir densamma.

1061
00:54:13,210 --> 00:54:14,120
>> JASON Hirschhorn: Så
börden förblir densamma.

1062
00:54:14,120 --> 00:54:16,040
Om vi ​​söker vänster, vi är
använder samma början -

1063
00:54:16,040 --> 00:54:16,860
exakt rätt.

1064
00:54:16,860 --> 00:54:17,870
Och det slutar?

1065
00:54:17,870 --> 00:54:19,390
Tyvärr, vad betyder det
slutar lika igen?

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
Nu, varför minus 1, inte bara mitt?

1069
00:54:23,470 --> 00:54:32,870

1070
00:54:32,870 --> 00:54:35,570
>> STUDENTEN Den mellersta är ur
bilden redan, eftersom vi hade

1071
00:54:35,570 --> 00:54:36,700
kontrollerat att den är ute?

1072
00:54:36,700 --> 00:54:37,630
>> JASON Hirschhorn: Det är
exakt rätt.

1073
00:54:37,630 --> 00:54:38,580
Den mellersta är ute ur bilden.

1074
00:54:38,580 --> 00:54:39,800
Vi kontrollerade redan i mitten.

1075
00:54:39,800 --> 00:54:44,730
Så vi vill inte "mitt" citat
unquote, att fortsätta att vara i

1076
00:54:44,730 --> 00:54:46,110
array som vi söker.

1077
00:54:46,110 --> 00:54:47,670
Så det här är fantastiskt.

1078
00:54:47,670 --> 00:54:50,670
>> Else om värden fäste mitten är större
än värdet slutar jämlikar

1079
00:54:50,670 --> 00:54:51,920
mitt minus 1.

1080
00:54:51,920 --> 00:54:55,060

1081
00:54:55,060 --> 00:54:57,340
Jeff, hur är detta sista raden?

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
Värden mitten är mindre än värdet?

1085
00:55:06,000 --> 00:55:07,570
>> JASON Hirschhorn: Vi ska
du ger mig annat.

1086
00:55:07,570 --> 00:55:09,310
Så om du inte ger mig -

1087
00:55:09,310 --> 00:55:12,270
>> STUDENT: Så då börjar
skulle vara mitt plus 1.

1088
00:55:12,270 --> 00:55:16,100

1089
00:55:16,100 --> 00:55:19,070
>> JASON Hirschhorn: Början jämlikar
mitten plus 1, återigen, för samma

1090
00:55:19,070 --> 00:55:20,820
Anledningen till att Constantine
gav oss tidigare.

1091
00:55:20,820 --> 00:55:24,280
Och i slutet, har som inte gett
mig en kodrad ännu?

1092
00:55:24,280 --> 00:55:26,600
Returnera false, Aleha, vad
vi skriver här?

1093
00:55:26,600 --> 00:55:28,590
>> STUDENTEN returnera false.

1094
00:55:28,590 --> 00:55:29,320
>> JASON Hirschhorn: returnera false.

1095
00:55:29,320 --> 00:55:33,340
Och vi måste göra det, för om vi
inte att den är, måste vi säga att vi

1096
00:55:33,340 --> 00:55:34,080
hittade inte det.

1097
00:55:34,080 --> 00:55:36,270
Och vi sa att vi ska gå tillbaka en
bool, så vi har definitivt återvända

1098
00:55:36,270 --> 00:55:38,150
en bool någonstans.

1099
00:55:38,150 --> 00:55:42,590
>> Så låt oss köra den här koden.

1100
00:55:42,590 --> 00:55:44,520
Jag är faktiskt tänker -

1101
00:55:44,520 --> 00:55:45,930
så vi är i terminalen.

1102
00:55:45,930 --> 00:55:47,230
Vi ska klara vårt fönster.

1103
00:55:47,230 --> 00:55:49,270
Låt oss göra allt.

1104
00:55:49,270 --> 00:55:50,340
Vi fann att det finns ett fel.

1105
00:55:50,340 --> 00:55:54,280
Det finns ett fel på rad 15, förväntas
semikolon i slutet av

1106
00:55:54,280 --> 00:55:54,890
deklaration.

1107
00:55:54,890 --> 00:55:56,454
Så vad har jag glömt?

1108
00:55:56,454 --> 00:55:57,230
>> STUDENT: Semikolon.

1109
00:55:57,230 --> 00:56:00,200
>> JASON Hirschhorn: Semikolon
rätt upp här.

1110
00:56:00,200 --> 00:56:00,950
Jag tror att det var Toms kod.

1111
00:56:00,950 --> 00:56:01,870
Så Tom, [OHÖRBAR].

1112
00:56:01,870 --> 00:56:03,120
Skojar bara.

1113
00:56:03,120 --> 00:56:05,010

1114
00:56:05,010 --> 00:56:07,310
Låt oss inte göra hela igen.

1115
00:56:07,310 --> 00:56:10,180
>> STUDENTEN Vad Dropbox katalog
bör vi vara på detta?

1116
00:56:10,180 --> 00:56:11,345
>> JASON Hirschhorn: Så du kan
bara titta på detta lite.

1117
00:56:11,345 --> 00:56:16,380
Men återigen, om du ville flytta detta
koda in din pset3 katalog för att försöka

1118
00:56:16,380 --> 00:56:17,050
ut, det är vad jag gjorde.

1119
00:56:17,050 --> 00:56:18,600
Om du kommer att märka här -
ledsen, bra fråga.

1120
00:56:18,600 --> 00:56:19,460
>> [? LS,?]

1121
00:56:19,460 --> 00:56:24,700
Jag har här på find.c koden
från denna veckas distro kod.

1122
00:56:24,700 --> 00:56:26,300
Jag har helpers.h.

1123
00:56:26,300 --> 00:56:30,010
Jag har en Make-fil som jag faktiskt
redigerade lite för att inkludera dessa nya

1124
00:56:30,010 --> 00:56:30,710
filer vi skriver.

1125
00:56:30,710 --> 00:56:34,120
Allt i denna lag kommer att finnas tillgänglig, inte
distributionskoden, men den nya

1126
00:56:34,120 --> 00:56:39,510
Gör filen, den nya helpers.h filen kommer
finnas tillgängliga på nätet för nedladdning.

1127
00:56:39,510 --> 00:56:41,800
Återigen, så de är de
extra koder vi har.

1128
00:56:41,800 --> 00:56:46,130
>> Så gör alla, per denna linje, gör hitta,
binär, val bubbla - märken

1129
00:56:46,130 --> 00:56:50,930
alla tre av dem och sammanställer i
denna körbar kod find.

1130
00:56:50,930 --> 00:56:54,090
Så generellt, vill vi inte
att direkt till check50.

1131
00:56:54,090 --> 00:56:57,580
Vi vill köra några tester på egen hand.

1132
00:56:57,580 --> 00:57:11,750
Men bara så att vi kan påskynda lite,
check50 2013 pset3.find kommer att passera

1133
00:57:11,750 --> 00:57:14,630
i helpers.c-- min dåliga.

1134
00:57:14,630 --> 00:57:16,050
>> Jag har inte det just nu.

1135
00:57:16,050 --> 00:57:20,670
Så vi faktiskt kommer att
köra koden på riktigt.

1136
00:57:20,670 --> 00:57:23,570
Usage.find /, vet du vad det betyder?

1137
00:57:23,570 --> 00:57:25,970
>> STUDENT: Du behöver en andra
kommandoraden på det.

1138
00:57:25,970 --> 00:57:26,980
>> JASON Hirschhorn: Jag behöver
en andra kommandorad.

1139
00:57:26,980 --> 00:57:30,640
Och per specifikationen, jag behöver
att ange vad vi letar efter.

1140
00:57:30,640 --> 00:57:33,750
Så låt oss titta efter 42.

1141
00:57:33,750 --> 00:57:37,030
Vi kommer att hålla den i sorterad, eftersom vi
har inte skrivit ännu en sorteringsfunktion -

1142
00:57:37,030 --> 00:57:41,830
42, 43, 44.

1143
00:57:41,830 --> 00:57:46,240
>> Och Kontroll D inte hittar
nålen i höstacken.

1144
00:57:46,240 --> 00:57:46,505
Det är illa.

1145
00:57:46,505 --> 00:57:47,200
Det är definitivt där.

1146
00:57:47,200 --> 00:57:48,090
Låt oss prova något annat.

1147
00:57:48,090 --> 00:57:49,860
Kanske är det för att jag satte
det i början.

1148
00:57:49,860 --> 00:57:54,490
>> Låt oss göra 41, 42, 43.

1149
00:57:54,490 --> 00:57:55,012
Så där.

1150
00:57:55,012 --> 00:57:56,400
Man fann det.

1151
00:57:56,400 --> 00:58:00,040
Låt oss uttrycka det i slutet nu, bara
så att vi kan vara noggrann -

1152
00:58:00,040 --> 00:58:03,580
40, 41, 42.

1153
00:58:03,580 --> 00:58:05,760
Hittade inte nålen.

1154
00:58:05,760 --> 00:58:07,550
Så jag nämnde detta tidigare.

1155
00:58:07,550 --> 00:58:08,980
Tyvärr visste jag detta
skulle hända.

1156
00:58:08,980 --> 00:58:11,490
>> Men för pedagogiska ändamål,
det är bra att utforska den.

1157
00:58:11,490 --> 00:58:12,990
Det fungerar inte.

1158
00:58:12,990 --> 00:58:16,020
Av någon anledning, kan inte hitta den.

1159
00:58:16,020 --> 00:58:18,970
Vi vet vad som finns där, men
vi inte hitta den.

1160
00:58:18,970 --> 00:58:24,140
Så en sak vi kan göra är att gå igenom
GDB för att hitta den, men inte vem som helst,

1161
00:58:24,140 --> 00:58:27,850
utan att gå igenom GDB, ha en
känsla av var vi skruvas upp?

1162
00:58:27,850 --> 00:58:28,480
[? Madu? ?]

1163
00:58:28,480 --> 00:58:30,960
>> STUDENT: Jag tror att det kan bli när man slutar
är lika med början, och det är

1164
00:58:30,960 --> 00:58:33,090
bara en en-inslag listan.

1165
00:58:33,090 --> 00:58:35,560
Då är det bara ignorerar det istället
att faktiskt kontrollera det.

1166
00:58:35,560 --> 00:58:36,940
>> JASON Hirschhorn: Det är
exakt rätt.

1167
00:58:36,940 --> 00:58:41,110
När avslutningen är lika med början, gör vi
fortfarande har en del i vår lista?

1168
00:58:41,110 --> 00:58:42,480
>> STUDENT: Ja.

1169
00:58:42,480 --> 00:58:45,450
>> JASON Hirschhorn: Ja, i själva verket är vi
har en och endast en del.

1170
00:58:45,450 --> 00:58:50,500
Och det kommer sannolikt att hända när,
per koden som vi testade, vi är på

1171
00:58:50,500 --> 00:58:54,640
framför höstacken eller vid
slutet av höstack.

1172
00:58:54,640 --> 00:58:56,000
Det är där början och
slut kommer att lika

1173
00:58:56,000 --> 00:58:57,820
en, med binär sökning.

1174
00:58:57,820 --> 00:59:01,440
Så i dessa två fall är det inte fungerade,
eftersom sinande var lika med början.

1175
00:59:01,440 --> 00:59:06,030
>> Men om sinande är lika med början,
gör detta medan loop köra?

1176
00:59:06,030 --> 00:59:06,390
Det gör det inte.

1177
00:59:06,390 --> 00:59:08,660
Och vi kunde ha kontrollerat
det igen genom GDB.

1178
00:59:08,660 --> 00:59:14,000
Så hur kan vi åtgärda det här koden, eftersom
när medan slutar är lika med

1179
00:59:14,000 --> 00:59:16,070
början, vill vi också här
while-slinga för att köra.

1180
00:59:16,070 --> 00:59:18,620
>> Så vad fix kan vi göra till linje 18?

1181
00:59:18,620 --> 00:59:21,060
>> STUDENTEN [OHÖRBAR] är större
än eller lika med.

1182
00:59:21,060 --> 00:59:21,700
>> JASON Hirschhorn: Exakt rätt.

1183
00:59:21,700 --> 00:59:24,600
Medan sluttid är större än
eller lika med början.

1184
00:59:24,600 --> 00:59:27,300
Så nu ser vi till att få det
hörn fall i slutet.

1185
00:59:27,300 --> 00:59:27,870
Och låt oss se.

1186
00:59:27,870 --> 00:59:29,560
Låt oss köra det en gång till.

1187
00:59:29,560 --> 00:59:31,266
>> Låt oss göra allt.

1188
00:59:31,266 --> 00:59:33,910
Återigen måste du bara
följa med här.

1189
00:59:33,910 --> 00:59:36,280
Hitta 41 denna gång.

1190
00:59:36,280 --> 00:59:37,360
Bara hålla det konsekvent.

1191
00:59:37,360 --> 00:59:38,210
>> Hitta 42.

1192
00:59:38,210 --> 00:59:38,930
Låt oss uttrycka det i början -

1193
00:59:38,930 --> 00:59:41,630
42, 43, 44.

1194
00:59:41,630 --> 00:59:42,860
Vi fann det.

1195
00:59:42,860 --> 00:59:47,710
Så det var verkligen förändringen
vi behövde göra.

1196
00:59:47,710 --> 00:59:51,090
>> Det var en hel del kodning vi
precis gjorde, binär sökning.

1197
00:59:51,090 --> 00:59:55,760
Är det någon som har några frågor innan
Jag går vidare in i rader som vi skrev i

1198
00:59:55,760 --> 00:59:58,750
binär sökning, eller hur vi tänkte
ut vad vi räkna ut?

1199
00:59:58,750 --> 01:00:01,900

1200
01:00:01,900 --> 01:00:06,270
Innan vi går vidare vill jag också peka
att i stort, vi kartlagt

1201
01:00:06,270 --> 01:00:09,300
vår pseudo-kod en till
en på vår kod.

1202
01:00:09,300 --> 01:00:11,550
>> Vi hade så knepig sak
att räkna ut med

1203
01:00:11,550 --> 01:00:12,890
börjar och slutar.

1204
01:00:12,890 --> 01:00:17,380
Men hade ni inte listat ut det, du
skulle ha skrivit ganska mycket

1205
01:00:17,380 --> 01:00:20,740
identisk kod, med undantag för
de två översta raderna.

1206
01:00:20,740 --> 01:00:23,380
Och då skulle du ha insett när
du gjorde det i kontroller och fall som

1207
01:00:23,380 --> 01:00:24,840
du behöver något annat.

1208
01:00:24,840 --> 01:00:28,510
Så även om du hade följt vår
pseudo-kod rad för rad, skulle du har

1209
01:00:28,510 --> 01:00:31,130
fått alla utom två rader
koda du behövs för att skriva.

1210
01:00:31,130 --> 01:00:33,900
>> Och jag skulle vara villig att satsa att ni
skulle ha räknat ut det

1211
01:00:33,900 --> 01:00:37,940
ganska snabbt, att du behövs för att sätta
någon form av markör i det att räkna

1212
01:00:37,940 --> 01:00:39,190
reda på var du var.

1213
01:00:39,190 --> 01:00:41,540

1214
01:00:41,540 --> 01:00:44,550
Det igen, är kraften i att göra
pseudo-kod i förväg.

1215
01:00:44,550 --> 01:00:47,310
Så vi kan göra logiken först, och sedan
Vi kan oroa syntaxen.

1216
01:00:47,310 --> 01:00:51,470
>> Hade vi varit förvirrad om logiken
samtidigt som man försöker att skriva denna kod i C,

1217
01:00:51,470 --> 01:00:53,110
vi skulle ha fått alla trasslat till.

1218
01:00:53,110 --> 01:00:56,340
Och då vi skulle ställa frågor om
logik och syntax och meshning

1219
01:00:56,340 --> 01:00:57,320
dem alla tillsammans.

1220
01:00:57,320 --> 01:01:02,170
Och vi skulle ha blivit förlorade
i vad som kan snabbt bli en

1221
01:01:02,170 --> 01:01:04,000
mycket svårt problem.

1222
01:01:04,000 --> 01:01:08,680
Så låt oss gå vidare nu
till val av sort.

1223
01:01:08,680 --> 01:01:10,760
>> Vi har 20 minuter kvar.

1224
01:01:10,760 --> 01:01:14,130
Så jag har en känsla av att vi inte kommer att kunna
få igenom alla val slag

1225
01:01:14,130 --> 01:01:15,940
och bubbel sort.

1226
01:01:15,940 --> 01:01:20,670
Men låt oss åtminstone försöka
för att avsluta val sortera.

1227
01:01:20,670 --> 01:01:23,540
Så genomföra val sortera använder
Följande funktionsdeklarationen.

1228
01:01:23,540 --> 01:01:27,530
>> Återigen, detta tas från
problem set specifikation.

1229
01:01:27,530 --> 01:01:31,560
Int värden är konsoler, är
en array av heltal.

1230
01:01:31,560 --> 01:01:33,490
Och int.n är storleken på matrisen.

1231
01:01:33,490 --> 01:01:36,840
Urval sort går
att sortera denna array.

1232
01:01:36,840 --> 01:01:43,580
>> Så enligt vår mentala modell av val
sortera, vi drar -

1233
01:01:43,580 --> 01:01:47,720
Först går vi igenom listan den första
tid, hitta det minsta antalet,

1234
01:01:47,720 --> 01:01:52,860
lägga den i början, hitta den andra
minsta antal, lägga den i

1235
01:01:52,860 --> 01:01:56,380
andra plats om vi vill
sortera i stigande ordning.

1236
01:01:56,380 --> 01:01:58,440
Jag tänker inte tvinga dig att skriva
pseudo-kod just nu.

1237
01:01:58,440 --> 01:02:01,350
>> Men innan vi gör koden som en klass i
fem minuter, kommer vi att skriva

1238
01:02:01,350 --> 01:02:03,550
pseudo-kod så att vi har någon mening
om vart vi ska.

1239
01:02:03,550 --> 01:02:05,630
Så försök att skriva pseudokod
på egen hand.

1240
01:02:05,630 --> 01:02:08,610
Och sedan försöka vända det
pseudo-kod i kod.

1241
01:02:08,610 --> 01:02:10,740
Vi kommer att göra det som en grupp
i fem minuter.

1242
01:02:10,740 --> 01:02:32,560

1243
01:02:32,560 --> 01:02:33,895
>> Och naturligtvis, låt mig veta om
du har några frågor.

1244
01:02:33,895 --> 01:03:56,738

1245
01:03:56,738 --> 01:03:58,230
>> STUDENT: Att det?

1246
01:03:58,230 --> 01:04:00,280
>> JASON Hirschhorn: Se hur långt du
kan komma i två minuter.

1247
01:04:00,280 --> 01:04:01,790
Jag förstår att du inte kommer
att kunna avsluta.

1248
01:04:01,790 --> 01:04:03,050
Men vi kommer att gå över det här som en grupp.

1249
01:04:03,050 --> 01:04:57,830

1250
01:04:57,830 --> 01:05:00,630
>> Du är all kodning så [OHÖRBAR], så jag är
ledsen att pausa det du gör.

1251
01:05:00,630 --> 01:05:02,530
Men låt oss gå igenom det här som en grupp.

1252
01:05:02,530 --> 01:05:07,590
Och återigen, binär sökning, ni alla ger
mig en om inte flera rader kod.

1253
01:05:07,590 --> 01:05:08,530
Tack för det.

1254
01:05:08,530 --> 01:05:11,730
Vi kommer att göra samma sak
här, kod tillsammans som en grupp.

1255
01:05:11,730 --> 01:05:15,170
>> Så val sort - låt oss skriva
några snabba pseudo-kod.

1256
01:05:15,170 --> 01:05:20,380
Per mental modell, kan någon ge mig
den första raden i pseudo-kod, tack?

1257
01:05:20,380 --> 01:05:23,000

1258
01:05:23,000 --> 01:05:24,270
Vad vill jag göra?

1259
01:05:24,270 --> 01:05:27,070
>> STUDENT: Även om listan
är i ordning.

1260
01:05:27,070 --> 01:05:30,630
>> JASON Hirschhorn: OK, medan
listan är i ordning.

1261
01:05:30,630 --> 01:05:33,540
Och vad menar du med "out of order?"

1262
01:05:33,540 --> 01:05:34,960
>> STUDENT: Även om [OHÖRBAR]

1263
01:05:34,960 --> 01:05:36,210
har inte sorterats.

1264
01:05:36,210 --> 01:05:38,460

1265
01:05:38,460 --> 01:05:40,290
>> JASON Hirschhorn: Medan listan
är ur funktion, vad gör vi?

1266
01:05:40,290 --> 01:05:44,200
Ge mig den andra raden,
snälla, Marcus.

1267
01:05:44,200 --> 01:05:47,186
>> STUDENT: Så hitta nästa
minsta talet.

1268
01:05:47,186 --> 01:05:49,000
Detta kommer att vara indragna.

1269
01:05:49,000 --> 01:05:55,140
>> JASON Hirschhorn: Så hittar
Nästa minsta talet.

1270
01:05:55,140 --> 01:05:56,460
Och sedan någon annan?

1271
01:05:56,460 --> 01:06:01,030
När vi hittar den näst minsta
nummer, vad gör vi?

1272
01:06:01,030 --> 01:06:03,010
Jag kommer att säga hitta
det minsta antalet.

1273
01:06:03,010 --> 01:06:04,820
Det är vad vi vill göra.

1274
01:06:04,820 --> 01:06:06,210
>> Så hitta det minsta antalet.

1275
01:06:06,210 --> 01:06:08,061
Men vad ska vi göra?

1276
01:06:08,061 --> 01:06:09,480
>> STUDENTEN [OHÖRBAR] till början.

1277
01:06:09,480 --> 01:06:10,680
>> JASON Hirschhorn: Förlåt?

1278
01:06:10,680 --> 01:06:12,700
>> STUDENT: Lägg den i
början av listan.

1279
01:06:12,700 --> 01:06:18,540
>> JASON Hirschhorn: Så placera den i
i början av listan.

1280
01:06:18,540 --> 01:06:20,140
Och vad gör vi med den saken
det var i början

1281
01:06:20,140 --> 01:06:20,830
på listan, eller hur?

1282
01:06:20,830 --> 01:06:21,910
Vi ska skriva över något.

1283
01:06:21,910 --> 01:06:23,130
Så var ska vi sätta det?

1284
01:06:23,130 --> 01:06:24,120
Ja, Anna?

1285
01:06:24,120 --> 01:06:25,520
>> STUDENT: Var det minsta
Antalet var?

1286
01:06:25,520 --> 01:06:32,530
>> JASON Hirshhorn: Så sätter början
av listan där

1287
01:06:32,530 --> 01:06:35,180
minsta talet var.

1288
01:06:35,180 --> 01:06:38,510
Så när listan är i ordning, hitta
det minsta antalet, placera den i

1289
01:06:38,510 --> 01:06:40,630
i början av listan, placera
början av listan där

1290
01:06:40,630 --> 01:06:42,900
minsta talet var.

1291
01:06:42,900 --> 01:06:45,780
Marcus, kan du formulera om denna linje
medan listan är ur funktion?

1292
01:06:45,780 --> 01:06:51,160

1293
01:06:51,160 --> 01:06:53,900
>> STUDENT: Även om siffrorna
har inte sorterats?

1294
01:06:53,900 --> 01:06:55,920
>> JASON Hirshhorn: OK, så för att
vet att siffrorna inte har varit

1295
01:06:55,920 --> 01:06:58,670
sorteras, vad behöver vi göra?

1296
01:06:58,670 --> 01:07:00,640
Hur mycket behöver vi
gå igenom den här listan?

1297
01:07:00,640 --> 01:07:09,650
>> STUDENT: Så jag antar att en for-loop, eller
samtidigt, medan siffrorna kontrolleras är mindre

1298
01:07:09,650 --> 01:07:11,900
än längden av listan?

1299
01:07:11,900 --> 01:07:13,160
>> JASON Hirshhorn: OK, det är bra.

1300
01:07:13,160 --> 01:07:15,000
Jag tror att jag misphrased
min fråga dåligt.

1301
01:07:15,000 --> 01:07:15,990
Jag försökte bara komma på
vi kommer att behöva gå

1302
01:07:15,990 --> 01:07:17,580
igenom hela listan.

1303
01:07:17,580 --> 01:07:20,490
Så medan listan är ur funktion,
för mig är svårt att kartlägga den.

1304
01:07:20,490 --> 01:07:24,940
Men i grund och botten, det är hur
Jag tycker om det här.

1305
01:07:24,940 --> 01:07:28,880
Gå igenom hela listan, hitta
minsta antalet, placera den i

1306
01:07:28,880 --> 01:07:30,130
början - faktiskt, du har rätt.

1307
01:07:30,130 --> 01:07:31,380
Låt oss sätta dem båda.

1308
01:07:31,380 --> 01:07:33,470

1309
01:07:33,470 --> 01:07:39,050
>> Så när listan är i ordning, vi
behöver gå igenom hela listan

1310
01:07:39,050 --> 01:07:42,250
gång, hitta det minsta antalet, plats
den i början av listan, sätta

1311
01:07:42,250 --> 01:07:45,430
början av listan där
minsta antal var, och sedan om den

1312
01:07:45,430 --> 01:07:47,460
Listan är fortfarande ur funktion, vi har
fick gå igenom detta

1313
01:07:47,460 --> 01:07:48,620
processen igen, eller hur?

1314
01:07:48,620 --> 01:07:51,610
Det är därför val sortera, Big-O runtime
av urvals sortera, någon?

1315
01:07:51,610 --> 01:07:52,830
>> STUDENT: n kvadrat.

1316
01:07:52,830 --> 01:07:53,590
>> JASON Hirshhorn: n i kvadrat.

1317
01:07:53,590 --> 01:07:57,040
Eftersom som Marcus och jag bara insåg
Här kommer vi att behöva

1318
01:07:57,040 --> 01:08:00,310
gå igenom listan listan
antal gånger.

1319
01:08:00,310 --> 01:08:03,420
Så gå igenom något av
längden n n antal gånger

1320
01:08:03,420 --> 01:08:04,990
är faktiskt n kvadrat.

1321
01:08:04,990 --> 01:08:08,100
>> Så det här är vår pseudokod.

1322
01:08:08,100 --> 01:08:09,360
Det ser mycket bra ut.

1323
01:08:09,360 --> 01:08:11,870
Är det någon som har några frågor
om pseudokoden?

1324
01:08:11,870 --> 01:08:14,440
Eftersom faktiskt urval sort bör
förmodligen komma 1-1, kod från

1325
01:08:14,440 --> 01:08:14,980
pseudokod.

1326
01:08:14,980 --> 01:08:17,569
Så några frågor om
logiken i pseudokoden?

1327
01:08:17,569 --> 01:08:18,819
Fråga nu.

1328
01:08:18,819 --> 01:08:22,609

1329
01:08:22,609 --> 01:08:25,379
>> Val av sort - medan listan är ute
av ordning, vi kommer att gå igenom den

1330
01:08:25,379 --> 01:08:27,529
och hitta den minsta varje gång
och lägga den i fronten.

1331
01:08:27,529 --> 01:08:33,470
Så medan listan är ur funktion, kan
någon ge mig den kodrad som

1332
01:08:33,470 --> 01:08:39,689
har inte gett mig en linje
av koden ännu, snälla?

1333
01:08:39,689 --> 01:08:40,939
Det låter som en vad?

1334
01:08:40,939 --> 01:08:43,669

1335
01:08:43,669 --> 01:08:44,649
>> STUDENT: Det är en for-loop.

1336
01:08:44,649 --> 01:08:45,830
>> JASON Hirshhorn: Det låter
gillar en for-loop.

1337
01:08:45,830 --> 01:08:47,653
OK, kan du ge mig den för loop?

1338
01:08:47,653 --> 01:08:48,925
For -

1339
01:08:48,925 --> 01:08:50,219
>> Elev: Jag är lika med 0.

1340
01:08:50,219 --> 01:08:52,705
>> JASON Hirshhorn: i eller -

1341
01:08:52,705 --> 01:08:55,111
Vad är det vi saknar?

1342
01:08:55,111 --> 01:08:56,819
Vad går just här?

1343
01:08:56,819 --> 01:08:57,550
>> STUDENT: Int.

1344
01:08:57,550 --> 01:08:59,270
>> JASON Hirshhorn: Exakt.

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 det, Jeff.

1348
01:09:09,319 --> 01:09:10,660
Vi går igenom listan, eller hur?

1349
01:09:10,660 --> 01:09:11,880
Vi har sett att koden innan.

1350
01:09:11,880 --> 01:09:12,850
Perfect.

1351
01:09:12,850 --> 01:09:14,790
Så låt oss sätta våra klammerparenteserna här.

1352
01:09:14,790 --> 01:09:17,859
Jag kommer att lägga en del
krullparenteser här.

1353
01:09:17,859 --> 01:09:21,660
>> Så även om det är 0, vi måste gå
igenom hela listan.

1354
01:09:21,660 --> 01:09:26,612
Så varje gång vi går igenom listan,
vad vill vi att hålla reda på?

1355
01:09:26,612 --> 01:09:28,260
>> STUDENT: Om några swappar görs.

1356
01:09:28,260 --> 01:09:29,069
>> JASON Hirshhorn: Hitta
det minsta antalet.

1357
01:09:29,069 --> 01:09:31,479
Så vi bör nog hålla koll på
det minsta antalet varje gång.

1358
01:09:31,479 --> 01:09:34,590
Så linje kan jag göra för att hålla koll
av det minsta antalet?

1359
01:09:34,590 --> 01:09:37,720
Aleha, hur kan jag behålla
koll på någonting?

1360
01:09:37,720 --> 01:09:38,460
>> STUDENT: Starta en ny variabel.

1361
01:09:38,460 --> 01:09:39,390
>> JASON Hirshhorn: Starta en ny variabel.

1362
01:09:39,390 --> 01:09:40,069
Så låt oss skapa en variabel.

1363
01:09:40,069 --> 01:09:41,830
Vilken typ?

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
Låt oss kalla det det minsta.

1367
01:09:44,939 --> 01:09:47,600
Och vad gör det lika när
vi just har börjat?

1368
01:09:47,600 --> 01:09:48,910
Vi har inte gått igenom listan ännu.

1369
01:09:48,910 --> 01:09:50,540
Vi är på den första delen av
lista vår första gången igenom.

1370
01:09:50,540 --> 01:09:51,930
Vad gör det lika,
minsta antal?

1371
01:09:51,930 --> 01:09:54,140
>> STUDENTEN värden som jag.

1372
01:09:54,140 --> 01:09:54,900
>> JASON Hirshhorn: värden som jag.

1373
01:09:54,900 --> 01:09:56,980
Det låter precis rätt, eller hur?

1374
01:09:56,980 --> 01:09:59,590
Det minsta antalet i början
är där vi är.

1375
01:09:59,590 --> 01:10:01,960
Så nu har vi vår minsta, och vi behöver
att gå igenom hela listan och

1376
01:10:01,960 --> 01:10:05,080
jämföra detta minsta
till allt annat.

1377
01:10:05,080 --> 01:10:08,150
Så går vi igenom listan igen?

1378
01:10:08,150 --> 01:10:08,630
Michael?

1379
01:10:08,630 --> 01:10:10,000
>> STUDENT: Du måste göra
annan för slinga.

1380
01:10:10,000 --> 01:10:10,383
>> JASON Hirshhorn: Another för slinga.

1381
01:10:10,383 --> 01:10:11,276
Låt oss göra det.

1382
01:10:11,276 --> 01:10:12,540
Ge mig lite kod.

1383
01:10:12,540 --> 01:10:13,790
>> STUDENT: För loop -

1384
01:10:13,790 --> 01:10:16,750

1385
01:10:16,750 --> 01:10:19,470
för de minsta -

1386
01:10:19,470 --> 01:10:23,040

1387
01:10:23,040 --> 01:10:25,770
bara int j, kan man säga?

1388
01:10:25,770 --> 01:10:31,150
= 0, så att -

1389
01:10:31,150 --> 01:10:34,014

1390
01:10:34,014 --> 01:10:35,710
>> JASON Hirshhorn: Tja, om vi vill
att gå igenom hela listan -

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
Vi kommer att gå igenom
den för slingan igen.

1395
01:10:46,100 --> 01:10:51,380
Och hur ska vi hitta
minsta antal?

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
Vi har den nuvarande minsta antalet,
så hur ska vi hitta nya minsta?

1399
01:11:00,520 --> 01:11:07,200
>> STUDENT: Vi kan kontrollera om de minsta
antal vi har är större än

1400
01:11:07,200 --> 01:11:09,040
värden bygel j.

1401
01:11:09,040 --> 01:11:14,740
>> JASON Hirshhorn: Så om minsta är
högre än värden fäste j..

1402
01:11:14,740 --> 01:11:19,350
Så om vår nuvarande minsta
är större än -

1403
01:11:19,350 --> 01:11:21,770
Jag kommer att flytta dessa två linjer
av kod där ute för en sekund.

1404
01:11:21,770 --> 01:11:26,010
Eftersom innan vi gör något swapping, vi
behöver gå igenom hela listan.

1405
01:11:26,010 --> 01:11:28,880
Så här pseudo bör faktiskt
vara utanför den inre for-loop.

1406
01:11:28,880 --> 01:11:30,390
Så gå igenom hela listan.

1407
01:11:30,390 --> 01:11:34,520
Om minsta är större än
värden j sen då?

1408
01:11:34,520 --> 01:11:37,830
>> STUDENTEN Sedan minsta
är lika med värdena 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
En snabb fråga -

1412
01:11:44,580 --> 01:11:47,236
första gången vi går igenom denna slinga,
Jag kommer att vara lika med 0, är ​​j går

1413
01:11:47,236 --> 01:11:50,710
ska ha värdet 0 när vi kommer in här.

1414
01:11:50,710 --> 01:11:52,410
Så vi kommer att jämföra
ett antal till sig själv.

1415
01:11:52,410 --> 01:11:53,660
Är det effektivt?

1416
01:11:53,660 --> 01:11:57,260

1417
01:11:57,260 --> 01:11:58,390
Nej, det är inte riktigt effektivt.

1418
01:11:58,390 --> 01:12:02,915
Gör så vår j måste gå
från 0 till n varje gång?

1419
01:12:02,915 --> 01:12:06,310
Behöver vi alltid för att kontrollera
igenom hela listan?

1420
01:12:06,310 --> 01:12:06,520
[OHÖRBAR]?

1421
01:12:06,520 --> 01:12:07,564
>> STUDENT: Börja med i stället.

1422
01:12:07,564 --> 01:12:09,405
>> JASON Hirshhorn: j burk
börja med vad?

1423
01:12:09,405 --> 01:12:09,990
>> Elev: Jag.

1424
01:12:09,990 --> 01:12:13,040
>> JASON Hirshhorn: j kan börja med jag.

1425
01:12:13,040 --> 01:12:18,840
Så nu vi jämför med början
med den som vi är på.

1426
01:12:18,840 --> 01:12:21,020
Men även då, är det som
effektiv som möjligt?

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 verkar vara
den mest effektiva, eftersom vi

1429
01:12:25,420 --> 01:12:26,120
redan har jag.

1430
01:12:26,120 --> 01:12:28,100
Vi anger att eftersom
minsta i linje 15.

1431
01:12:28,100 --> 01:12:29,350
Vi ska börja med
nästa automatiskt.

1432
01:12:29,350 --> 01:12:34,470

1433
01:12:34,470 --> 01:12:38,540
Så vi går igenom för loopen.

1434
01:12:38,540 --> 01:12:39,620
Vi går igenom varje gång.

1435
01:12:39,620 --> 01:12:40,860
Vi kommer att gå igenom ett antal gånger.

1436
01:12:40,860 --> 01:12:42,860
Nu har vi fått genom
denna inre för slinga.

1437
01:12:42,860 --> 01:12:44,350
Vi har det minsta värdet sparas.

1438
01:12:44,350 --> 01:12:46,045
Vi måste hålla den mot det
början av listan.

1439
01:12:46,045 --> 01:12:48,390
Så hur gör jag det på
början av listan?

1440
01:12:48,390 --> 01:12:51,290

1441
01:12:51,290 --> 01:12:55,926
Vad är den variabel som refererar
till början av listan?

1442
01:12:55,926 --> 01:13:00,500
Vi är i den här utanför för slinga,
så vad avser det

1443
01:13:00,500 --> 01:13:01,280
början av listan?

1444
01:13:01,280 --> 01:13:02,880
>> STUDENTEN värden som jag.

1445
01:13:02,880 --> 01:13:03,510
>> JASON Hirshhorn: Exakt rätt.

1446
01:13:03,510 --> 01:13:04,650
Värden i är början av den -

1447
01:13:04,650 --> 01:13:06,320
eller ledsen, inte i början.

1448
01:13:06,320 --> 01:13:07,090
Det var förvirrande.

1449
01:13:07,090 --> 01:13:11,620
Det är där vi är i början av
den osorterade delen av listan.

1450
01:13:11,620 --> 01:13:12,800
Så värderar jag.

1451
01:13:12,800 --> 01:13:14,050
Och vad betyder det lika?

1452
01:13:14,050 --> 01:13:15,925

1453
01:13:15,925 --> 01:13:17,326
>> STUDENT: Minsta.

1454
01:13:17,326 --> 01:13:18,862
>> JASON Hirshhorn: Värden i lika vad?

1455
01:13:18,862 --> 01:13:19,310
>> STUDENT: Minsta.

1456
01:13:19,310 --> 01:13:20,030
>> JASON Hirshhorn: Minsta.

1457
01:13:20,030 --> 01:13:20,980
Exakt rätt.

1458
01:13:20,980 --> 01:13:23,510
Så vi placera den i början
av listan, och nu måste vi sätta

1459
01:13:23,510 --> 01:13:25,710
början av listan där
det minsta antalet var.

1460
01:13:25,710 --> 01:13:29,700
Så hur skriver jag där
minsta talet var?

1461
01:13:29,700 --> 01:13:31,670
Värden på vad?

1462
01:13:31,670 --> 01:13:33,170
>> STUDENT: 0.

1463
01:13:33,170 --> 01:13:34,090
>> JASON Hirshhorn: Den lilla
nummer är på 0?

1464
01:13:34,090 --> 01:13:35,340
>> STUDENT: Ja.

1465
01:13:35,340 --> 01:13:38,680

1466
01:13:38,680 --> 01:13:39,910
>> JASON Hirshhorn: Vad händer om de minsta
Antalet var vid slutet av

1467
01:13:39,910 --> 01:13:40,860
detta osorterad lista?

1468
01:13:40,860 --> 01:13:42,460
>> STUDENT: Förlåt, vad var frågan?

1469
01:13:42,460 --> 01:13:44,020
>> JASON Hirshhorn: Var är
det minsta antalet?

1470
01:13:44,020 --> 01:13:46,940
Vi tog den minsta och lägga den på
början, med denna linje här.

1471
01:13:46,940 --> 01:13:48,987
>> STUDENT: Det borde ha
lagrats i vissa -

1472
01:13:48,987 --> 01:13:50,510
>> STUDENT: Värden j.

1473
01:13:50,510 --> 01:13:51,520
>> JASON Hirshhorn: Tja, det är
inte nödvändigtvis värden j..

1474
01:13:51,520 --> 01:13:54,100
Det behöver inte ens existerar på denna punkt.

1475
01:13:54,100 --> 01:13:55,960
>> STUDENT: Du måste deklarera
en variabel tidigare och

1476
01:13:55,960 --> 01:13:58,230
tilldela den till -

1477
01:13:58,230 --> 01:14:01,150
när du hittar det minsta antalet,
tilldela index för det numret till

1478
01:14:01,150 --> 01:14:02,480
viss variabel eller något liknande.

1479
01:14:02,480 --> 01:14:04,790
>> JASON Hirshhorn: Så kan
du säga det igen?

1480
01:14:04,790 --> 01:14:08,390
>> STUDENT: Så var du deklarerat int
minsta, bör du också deklarera int

1481
01:14:08,390 --> 01:14:10,750
minsta index = i, eller
något liknande.

1482
01:14:10,750 --> 01:14:13,280
>> JASON Hirshhorn: Så där jag tror int
minsta, ska jag inte bara hålla reda

1483
01:14:13,280 --> 01:14:16,150
av värdet men platsen.

1484
01:14:16,150 --> 01:14:20,850
int smallest_location = i detta
fallet, vi bara gör jag.

1485
01:14:20,850 --> 01:14:22,390
Vi måste veta var det är.

1486
01:14:22,390 --> 01:14:26,820
Vi fick till slutet av koden, och vi
insåg vi hade ingen aning om var det var.

1487
01:14:26,820 --> 01:14:29,810
Och så igen, vi är kartläggning
detta på 00:59.

1488
01:14:29,810 --> 01:14:32,890
Ni som kodar detta på din egen vilja
förmodligen få samma problem.

1489
01:14:32,890 --> 01:14:34,130
Hur sjutton hittar jag den?

1490
01:14:34,130 --> 01:14:36,720
Och då inser man, vänta, jag
behöver för att hålla reda på det.

1491
01:14:36,720 --> 01:14:38,500
>> Så om minsta är större
än värdena j.

1492
01:14:38,500 --> 01:14:39,740
Vi satt minsta lika med värden j..

1493
01:14:39,740 --> 01:14:42,090
Vad mer behöver vi förändra?

1494
01:14:42,090 --> 01:14:43,710
Constantin, vad annars göra
Vi behöver ändra?

1495
01:14:43,710 --> 01:14:44,560
>> STUDENT: Läget.

1496
01:14:44,560 --> 01:14:45,270
>> JASON Hirshhorn: Exakt.

1497
01:14:45,270 --> 01:14:46,925
Så ge mig den linjen i kod.

1498
01:14:46,925 --> 01:14:53,310
>> STUDENTEN smallest_location = j.

1499
01:14:53,310 --> 01:14:54,790
>> JASON Hirshhorn: Exakt.

1500
01:14:54,790 --> 01:14:58,210
Och sedan ner i slutet, om vi vill
satte i början av listan där

1501
01:14:58,210 --> 01:15:00,790
det minsta antalet var, hur
vi hänvisar till var

1502
01:15:00,790 --> 01:15:02,200
minsta talet var?

1503
01:15:02,200 --> 01:15:03,580
Marcus?

1504
01:15:03,580 --> 01:15:08,530
>> STUDENT: Det minsta antalet var
ligger på minsta plats.

1505
01:15:08,530 --> 01:15:12,230
>> JASON Hirshhorn: Så vid värden
smallest_location.

1506
01:15:12,230 --> 01:15:14,700
Och vad har vi lagt där?

1507
01:15:14,700 --> 01:15:17,600
I början av
listan, vad är det?

1508
01:15:17,600 --> 01:15:19,710
>> STUDENT: Tja, vet vi inte riktigt vet
längre eftersom vi skrivit över.

1509
01:15:19,710 --> 01:15:23,250
Så det är ett bytte platser
av dessa två rader?

1510
01:15:23,250 --> 01:15:26,110
Om du byter dessa två linjer runt.

1511
01:15:26,110 --> 01:15:30,740
>> JASON Hirshhorn: OK, så vi gör inte
längre, eftersom vi återställa linjen

1512
01:15:30,740 --> 01:15:31,960
innan värden jag till minsta.

1513
01:15:31,960 --> 01:15:33,810
Så vi förlorade det ursprungliga värdet.

1514
01:15:33,810 --> 01:15:37,350
Så du sa att byta dessa två linjer.

1515
01:15:37,350 --> 01:15:41,780
Så nu satte i början av listan
där det minsta antalet var.

1516
01:15:41,780 --> 01:15:47,060
Så smallest_location lika värden i..

1517
01:15:47,060 --> 01:15:51,310
Det rör sig i början av detta
osorterade delen av listan till

1518
01:15:51,310 --> 01:15:52,090
minsta läge.

1519
01:15:52,090 --> 01:15:54,860
Och sedan in i värden jag vi flyttar
det minsta talet.

1520
01:15:54,860 --> 01:15:57,450
>> Låter det vettigt att vi
var tvungen att göra det swap?

1521
01:15:57,450 --> 01:15:59,650
Vi skulle ha skrivits över det värdet -
en annan sak du förmodligen skulle ha

1522
01:15:59,650 --> 01:16:02,740
räknat ut och fann i BNP.

1523
01:16:02,740 --> 01:16:05,310
Så vi har tagit hand om
all pseudokod.

1524
01:16:05,310 --> 01:16:10,935
Finns det något annat vi
behöver skriva här?

1525
01:16:10,935 --> 01:16:14,911
Kan någon komma på något?

1526
01:16:14,911 --> 01:16:16,180
>> STUDENT: Hur vet du
när du är klar?

1527
01:16:16,180 --> 01:16:17,680
>> JASON Hirshhorn: Hur gör vi
vet när vi är klara?

1528
01:16:17,680 --> 01:16:18,890
Bra fråga.

1529
01:16:18,890 --> 01:16:21,684
Så hur vet vi när vi är klara.

1530
01:16:21,684 --> 01:16:24,720
>> STUDENT: Skapa en variabel för att hålla räkningen
av om det finns en swap gjort eller inte

1531
01:16:24,720 --> 01:16:27,810
och går igenom ett pass.

1532
01:16:27,810 --> 01:16:30,180
>> JASON Hirshhorn: OK.

1533
01:16:30,180 --> 01:16:31,800
Det skulle fungera i bubbel sort.

1534
01:16:31,800 --> 01:16:35,210
Men för urvalet sortera, om vi inte
göra en swap, kan det bara vara

1535
01:16:35,210 --> 01:16:38,670
eftersom det minsta värdet är
i det dess rätt plats.

1536
01:16:38,670 --> 01:16:41,240
Vi kanske har en lista 1, 2, 4, 3.

1537
01:16:41,240 --> 01:16:42,830
Den andra gången vi
kommer inte att göra några swappar.

1538
01:16:42,830 --> 01:16:47,260
Vi kommer att vara på nummer 2, men vi ska
fortfarande behöver för att hålla igång.

1539
01:16:47,260 --> 01:16:49,390
Så behöver vi för att hålla reda på när
vi är klara, eller vill vi bara att gå

1540
01:16:49,390 --> 01:16:50,640
tills det är klart?

1541
01:16:50,640 --> 01:16:54,098

1542
01:16:54,098 --> 01:16:56,740
>> STUDENT: Vi kan bara gå
tills den är klar.

1543
01:16:56,740 --> 01:16:58,090
>> JASON Hirshhorn: Vi kan bara
gå tills det är klart.

1544
01:16:58,090 --> 01:17:01,720
I bubbel sortera, du är precis rätt,
Jeff och Aleha, med din lösning -

1545
01:17:01,720 --> 01:17:04,990
det är bra att hålla reda på hur många
swappar du gjort, för i bubblan

1546
01:17:04,990 --> 01:17:07,920
sortera, om du gör det i själva verket gör inga swappar,
du är klar och du kan kanske minska din

1547
01:17:07,920 --> 01:17:09,000
Problemet ner lite.

1548
01:17:09,000 --> 01:17:11,440
Men för urvalet sortera, har du verkligen
fick gå fram till slutet av den

1549
01:17:11,440 --> 01:17:14,940
lista varje gång.

1550
01:17:14,940 --> 01:17:16,200
>> Så det här är det.

1551
01:17:16,200 --> 01:17:18,530
Vi har två minuter kvar.

1552
01:17:18,530 --> 01:17:21,560
Låt oss göra allt.

1553
01:17:21,560 --> 01:17:24,340
Låt mig bara öppet Hitta hit och göra
säker på att jag faktiskt ringer upp -

1554
01:17:24,340 --> 01:17:25,610
Jag tänker inte kalla bubbla sortera.

1555
01:17:25,610 --> 01:17:29,230
Låt oss ändra detta till val slag.

1556
01:17:29,230 --> 01:17:31,060
göra allt. / hitta.

1557
01:17:31,060 --> 01:17:32,360
Låt oss hitta 42.

1558
01:17:32,360 --> 01:17:38,110
Den här gången ska vi passera en
osorterad lista, eftersom det borde sortera

1559
01:17:38,110 --> 01:17:43,790
första, per fyndet kod - bör sortera
först med hjälp av vår sorteringsfunktion och sedan

1560
01:17:43,790 --> 01:17:44,995
leta efter något.

1561
01:17:44,995 --> 01:17:46,245
Tummarna alla.

1562
01:17:46,245 --> 01:17:48,530

1563
01:17:48,530 --> 01:17:49,370
>> Åh herregud.

1564
01:17:49,370 --> 01:17:50,800
Whoa, fick mitt hjärta att slå.

1565
01:17:50,800 --> 01:17:52,320
Så det är korrekt.

1566
01:17:52,320 --> 01:17:57,270
Faktum är att om vi körde detta mer
utsträckning, koden, så vitt jag kan

1567
01:17:57,270 --> 01:17:59,280
berätta, är helt rätt.

1568
01:17:59,280 --> 01:18:02,150
Det finns några förslag
Jag vill ha dig.

1569
01:18:02,150 --> 01:18:06,215
Till exempel, 15 och 16 verkar
lite överflödig.

1570
01:18:06,215 --> 01:18:09,450
Det verkar som att du inte nödvändigtvis
måste spara både dem.

1571
01:18:09,450 --> 01:18:12,790
Om du har den minsta plats, du
kan lätt hitta det minsta värdet av

1572
01:18:12,790 --> 01:18:14,750
bara skriva värden på i.

1573
01:18:14,750 --> 01:18:18,100
>> Så om jag skulle klassificera din kod,
som jag faktiskt kommer att vara, skulle jag

1574
01:18:18,100 --> 01:18:21,160
förmodligen ta bort en punkt om du
ingår båda dessa, eftersom du

1575
01:18:21,160 --> 01:18:22,670
behöver inte båda dessa.

1576
01:18:22,670 --> 01:18:25,400
Om du har plats kan du
mycket lätt få värdet.

1577
01:18:25,400 --> 01:18:27,520
Och det verkar lite konstigt
att lagra dem båda.

1578
01:18:27,520 --> 01:18:31,070
Kanske inte ens ta en punkt, men
säkert kommentera att det är kanske

1579
01:18:31,070 --> 01:18:32,670
inte ett stilist val
du måste göra.

1580
01:18:32,670 --> 01:18:35,290
Naturligtvis koden fortfarande
går alldeles utmärkt.

1581
01:18:35,290 --> 01:18:36,860
>> Så tyvärr gjorde vi inte
få att bubbla slag.

1582
01:18:36,860 --> 01:18:37,940
Jag är ledsen för det.

1583
01:18:37,940 --> 01:18:39,135
Vi gjorde slut val sort.

1584
01:18:39,135 --> 01:18:41,450
Är det någon som har några sista frågor
om val av sort?

1585
01:18:41,450 --> 01:18:44,320

1586
01:18:44,320 --> 01:18:47,690
>> OK, innan vi beger oss ut, jag vill ha dig
att öppna upp din Chrome webbläsare.

1587
01:18:47,690 --> 01:18:54,340
Tyvärr var det bara ett flagrant plugg
för en typ av webbläsare.

1588
01:18:54,340 --> 01:18:57,770
Du kan öppna upp någon typ av webbläsare,
men det kommer förmodligen att Chrome.

1589
01:18:57,770 --> 01:19:01,250
Och gå till följande webbplats -

1590
01:19:01,250 --> 01:19:06,410
sayat.me/cs50.

1591
01:19:06,410 --> 01:19:07,685
Om du inte skriver i din dator
just nu, är du helt klart

1592
01:19:07,685 --> 01:19:10,210
inte gör det, Tom.

1593
01:19:10,210 --> 01:19:12,870
>> Och var snäll och gör det heller rätt
nu eller i nästa timme -

1594
01:19:12,870 --> 01:19:14,260
ge mig lite feedback.

1595
01:19:14,260 --> 01:19:15,660
Det här är bara avsnitt två.

1596
01:19:15,660 --> 01:19:18,060
Vi har många fler tillsammans, så jag
har ett stort utrymme för att förbättra.

1597
01:19:18,060 --> 01:19:19,620
Jag förhoppningsvis också gjorde vissa saker bra.

1598
01:19:19,620 --> 01:19:22,160
Så du kan få mig att må dåligt, men om
du också vill ge mig en smiley

1599
01:19:22,160 --> 01:19:24,250
ansikte, skulle jag uppskatta det också.

1600
01:19:24,250 --> 01:19:25,330
Fylla den i.

1601
01:19:25,330 --> 01:19:28,210
>> Och med en minut kvar,
det var vecka tre.

1602
01:19:28,210 --> 01:19:30,750
Jag ska stå utanför för lite
Om du har några frågor.

1603
01:19:30,750 --> 01:19:32,220
Jag kommer att se er i
föreläsning imorgon.

1604
01:19:32,220 --> 01:19:34,742