1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binariae Quaero]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Harvard University]

3
00:00:04,000 --> 00:00:07,000
[Hoc est CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Si ego dedi vobis a album of Disney character nomina in ordinem alphabeti

5
00:00:09,000 --> 00:00:11,000
et interrogavit vobis invenire Mickey Mus,

6
00:00:11,000 --> 00:00:13,000
quomodo vis ire circa haec facis

7
00:00:13,000 --> 00:00:15,000
Unum obvious modo, ad lustrandum list ab initio

8
00:00:15,000 --> 00:00:18,000
et coercere omne nomen, ut videret si suus 'Mickey.

9
00:00:18,000 --> 00:00:22,000
Sed habes Aladdin Alicia Arihel et cetera,

10
00:00:22,000 --> 00:00:25,000
mox inde in fronte intellego te non lectus utilem.

11
00:00:25,000 --> 00:00:29,000
Bene, fortasse retro a fine facientes initium elit.

12
00:00:29,000 --> 00:00:33,000
Nunc legistis Tarzan, CONSUO Nix White, et sic porro.

13
00:00:33,000 --> 00:00:36,000
Tamen ut non videatur sicut eam melius.

14
00:00:36,000 --> 00:00:38,000
>> Bene, quod aliter est de ea re conari posse contrahere

15
00:00:38,000 --> 00:00:41,000
Tu vide indicem nominum.

16
00:00:41,000 --> 00:00:43,000
Cum scias quod in litteras,

17
00:00:43,000 --> 00:00:45,000
aspicite in medio possis indice nominum

18
00:00:45,000 --> 00:00:49,000
nisi prius aut posterius nomen reprehendo amet dolore.

19
00:00:49,000 --> 00:00:51,000
In nibh nibh intuentes

20
00:00:51,000 --> 00:00:54,000
youd 'animadverto ut M pro Mickey venit post J pro Jasmine,

21
00:00:54,000 --> 00:00:57,000
sic youd simpliciter ignoratorum primoris dimidium of album.

22
00:00:57,000 --> 00:00:59,000
Tunc youd 'forsit, respice ad verticem ultima columna

23
00:00:59,000 --> 00:01:02,000
et vide quia incipit cum Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey venit ante Rapunzel, vultusface, amo nos neglegat ultima columna pariter.

25
00:01:06,000 --> 00:01:08,000
Exsequenti quaero rationem belli, youll 'velociter animadverto ut Mickey

26
00:01:08,000 --> 00:01:11,000
Prima pars cetera nomina in albo

27
00:01:11,000 --> 00:01:14,000
et tandem inveniet Mickey latitantes inter Merlini et Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Quid vos iustus faciebat basically binariae search.

29
00:01:17,000 --> 00:01:22,000
Ut hoc nomen importat, fungatur eius indagando militarium in binarii materia.

30
00:01:22,000 --> 00:01:24,000
Quid hoc sibi vult?

31
00:01:24,000 --> 00:01:27,000
Bene, dato a album of sorted items, binariae search algorithm facit binariae decisionem -

32
00:01:27,000 --> 00:01:33,000
laeva sive dextera, majus aut minus, prius et posterius alphabetically - in singulis.

33
00:01:33,000 --> 00:01:35,000
Hic jam quaeritur nomen algorithm it,

34
00:01:35,000 --> 00:01:38,000
Intueamur ergo aliud, sed cum digestus indicem numerorum.

35
00:01:38,000 --> 00:01:43,000
Dicunt, nos exspectantes numerus CXLIV in hoc album of sorted numerorum.

36
00:01:43,000 --> 00:01:46,000
Sicut prius est invenire numerum media -

37
00:01:46,000 --> 00:01:50,000
quo in casu XIII - XIII et minus quam si CXLIV.

38
00:01:50,000 --> 00:01:54,000
XIII maius est evidenter eo quod potest ignorare, quod omnia fere XIII

39
00:01:54,000 --> 00:01:57,000
et justum incumbo in residuam medietatem.

40
00:01:57,000 --> 00:01:59,000
Cum iam rebus par ad reliquum

41
00:01:59,000 --> 00:02:01,000
penitus media elige turba prope est.

42
00:02:01,000 --> 00:02:03,000
LV hic velimus.

43
00:02:03,000 --> 00:02:06,000
LXXXIX elegit tam facile possimus.

44
00:02:06,000 --> 00:02:11,000
Okay. Item, maior est CXLIV LV ita dextram.

45
00:02:11,000 --> 00:02:14,000
Fortunate pro nobis, sequenti numero medio est CXLIV,

46
00:02:14,000 --> 00:02:16,000
hunc quaeritis.

47
00:02:16,000 --> 00:02:21,000
Sic ut inveniret CXLIV usura a binariae search, sumus invenire poteritis, hoc solum in III steps.

48
00:02:21,000 --> 00:02:24,000
Si nos usi fuissent linearibus search, esset ceperint nobis XII steps.

49
00:02:24,000 --> 00:02:28,000
Adeo ut, cum quaeritur ratio sumpta ex rerum copia

50
00:02:28,000 --> 00:02:31,000
inspiciendum est ad quemlibet passum est item quaerens inveniet

51
00:02:31,000 --> 00:02:35,000
acta res in numero fere numero.

52
00:02:35,000 --> 00:02:37,000
II His exempla vidi, lets 'inspice

53
00:02:37,000 --> 00:02:41,000
quidam pseudocode pro recursive functio, ut effectum adducit binariae search.

54
00:02:41,000 --> 00:02:44,000
Summo amet videmus quod id quod pertinet ad quaerendum IV argumentorum

55
00:02:44,000 --> 00:02:47,000
clavis aciem min et Max.

56
00:02:47,000 --> 00:02:51,000
Quaeratur quot sit amet, ut in priore exemplo CXLIV.

57
00:02:51,000 --> 00:02:54,000
Indicem numerorum bellum quaerimus.

58
00:02:54,000 --> 00:02:57,000
Min et max sunt indices summam minimam et maximum positionum

59
00:02:57,000 --> 00:02:59,000
ut nos es currently aspiciendo.

60
00:02:59,000 --> 00:03:03,000
Cum imus min velit eget nulla erit repugnantia acies Max.

61
00:03:03,000 --> 00:03:07,000
Sicut et nos arta search descendit, nos mos update min et max

62
00:03:07,000 --> 00:03:10,000
Etiam ut elit rhoncus respiciens ad iustitiam

63
00:03:10,000 --> 00:03:12,000
>> Lets skip ad interesting pars prima.

64
00:03:12,000 --> 00:03:14,000
Nos invenire primum est medium,

65
00:03:14,000 --> 00:03:19,000
tum, quod medium inter maximum et minimum qui de acie adhuc considerare.

66
00:03:19,000 --> 00:03:22,000
Videamus quae deinde sedes valorem medium locum

67
00:03:22,000 --> 00:03:25,000
et si quaeratur numerus minor est clavis.

68
00:03:25,000 --> 00:03:27,000
Si numerus ad minorem locum,

69
00:03:27,000 --> 00:03:31,000
igitur maior sit amet sinistra numerorum dispositione.

70
00:03:31,000 --> 00:03:33,000
Sic possumus appellare, binariae quaero muneris iterum,

71
00:03:33,000 --> 00:03:36,000
tamen is vicis adaequationis ad min et max parametris legere iustus dimidiae

72
00:03:36,000 --> 00:03:40,000
Sicut pretium et paribus maior existit.

73
00:03:40,000 --> 00:03:44,000
Rursus, si minor numero amet nunc in medium agmen

74
00:03:44,000 --> 00:03:47,000
et sinistram volumus ignorare quod omnibus numeris auxerunt.

75
00:03:47,000 --> 00:03:52,000
Rursus, vocamus binariae search sed hoc tempus cum range of min et max Updated

76
00:03:52,000 --> 00:03:54,000
ad includantur dimidiae partis inferioris.

77
00:03:54,000 --> 00:03:57,000
Si valor ad current mediocritatem in, in aciem nec est

78
00:03:57,000 --> 00:04:01,000
nec minus maiora amet Ergo aequalis sit amet.

79
00:04:01,000 --> 00:04:05,000
Et sic possumus simpliciter redire current mediocritatem index, et nos 'perfectus.

80
00:04:05,000 --> 00:04:09,000
Denique hoc erit quod sequatur numerus

81
00:04:09,000 --> 00:04:11,000
quaerimus non numerorum seriem in actu.

82
00:04:11,000 --> 00:04:14,000
Maxime si quaeratur iugis index

83
00:04:14,000 --> 00:04:17,000
semper quam minimum excessisse diximus Id.

84
00:04:17,000 --> 00:04:20,000
Cum numerus non erat in input apparatu, revertamur -1

85
00:04:20,000 --> 00:04:24,000
Etiam non inveniebatur.

86
00:04:24,000 --> 00:04:26,000
>> Idque ut dictum algorithm operari

87
00:04:26,000 --> 00:04:28,000
elenchus, numerorum habet sorted.

88
00:04:28,000 --> 00:04:31,000
In aliis verbis, tantum modo cogitatione possumus invenire CXLIV usura binariae search

89
00:04:31,000 --> 00:04:34,000
si ab imo ad summum omnibus numeris ordinantur.

90
00:04:34,000 --> 00:04:38,000
Non hoc, non excludit partem numeri possent utraque gradum.

91
00:04:38,000 --> 00:04:40,000
Sic habemus II bene.

92
00:04:40,000 --> 00:04:43,000
Aut nos potest capere an Unsorted album quod exstat illud coram usura binariae search,

93
00:04:43,000 --> 00:04:48,000
aut possumus efficere ut nos commoda augere numerum numerorum multitudo est.

94
00:04:48,000 --> 00:04:50,000
Sic, pro voluptua iustus cum habeamus ut investigaret,

95
00:04:50,000 --> 00:04:53,000
cur non servant list sorted omni tempore?

96
00:04:53,000 --> 00:04:57,000
>> Unum via ut servo a album numerorum sorted dum simul præbens

97
00:04:57,000 --> 00:04:59,000
unum addere vel movere numerorum ex is album

98
00:04:59,000 --> 00:05:02,000
est per usura aliquid dicitur binariae search arbore.

99
00:05:02,000 --> 00:05:05,000
A binariae search arbor est notitia revoluta quae habet III proprietates.

100
00:05:05,000 --> 00:05:09,000
Primo, sinistro subtree alicuius node continet tantummodo valores, qui sunt minus quam

101
00:05:09,000 --> 00:05:11,000
aut aequalis node scriptor valorem.

102
00:05:11,000 --> 00:05:15,000
Secundo, ius subtree of a node tantum continet valores, qui sunt maiores quam

103
00:05:15,000 --> 00:05:17,000
aut aequalis node scriptor valorem.

104
00:05:17,000 --> 00:05:20,000
Denique nodos omnis et dextra subtrees

105
00:05:20,000 --> 00:05:23,000
sunt etiam binariae search arboribus.

106
00:05:23,000 --> 00:05:26,000
Intueamur exemplum iisdem numeris supra usi sumus.

107
00:05:26,000 --> 00:05:30,000
Enim vobis eorum qui numquam vidimus a computer scientia arbor ante,

108
00:05:30,000 --> 00:05:34,000
permissum mihi incoeperunt per dico vos ut a computer scientia arbor deorsum.

109
00:05:34,000 --> 00:05:36,000
Yes, dissimiles arbores soletis,

110
00:05:36,000 --> 00:05:38,000
radix arboris scientiae eu superius,

111
00:05:38,000 --> 00:05:41,000
imo et folia.

112
00:05:41,000 --> 00:05:45,000
Singulis capsellam dicitur node, et nodorum sunt connexae ad invicem marginibus.

113
00:05:45,000 --> 00:05:48,000
Nodi igitur est huius arboris radix XIII quanti valoris,

114
00:05:48,000 --> 00:05:52,000
quae habet II filios nodis cum valores V et XXXIV.

115
00:05:52,000 --> 00:05:57,000
Solum est lignum formatum in subtree ordo universi visione arboris.

116
00:05:57,000 --> 00:06:03,000
>> Pro exemplo, sinistro subtree de node III est arbor creata a nodorum 0, I, et II.

117
00:06:03,000 --> 00:06:06,000
Si igitur inquisitio passiones binarii redire ad arborem

118
00:06:06,000 --> 00:06:09,000
node convenit inter omnes arbor videmus in III proprietatibus, scilicet

119
00:06:09,000 --> 00:06:15,000
sinistram subtree solum continet valores, qui sunt minus quam aut aequalis node scriptor valorem;

120
00:06:15,000 --> 00:06:16,000
ius subtree omnium nodorum

121
00:06:16,000 --> 00:06:19,000
tantum continet valores, qui sunt maiores quam aut aequalis node scriptor valorem; et

122
00:06:19,000 --> 00:06:25,000
utrumque dextra laevaque subtrees omnium nodorum quoque sunt binariae search arboribus.

123
00:06:25,000 --> 00:06:28,000
Licet hoc arbor spectat diversis, hoc validum est, binariae search arbor

124
00:06:28,000 --> 00:06:30,000
profectus eadem numero.

125
00:06:30,000 --> 00:06:32,000
Adeo ut multa modis efficere potest ut

126
00:06:32,000 --> 00:06:35,000
validum binariae search arbor ex his numerorum.

127
00:06:35,000 --> 00:06:38,000
Age, eamus ad nos prior crearetur.

128
00:06:38,000 --> 00:06:40,000
Quid ergo faciemus istis ligna

129
00:06:40,000 --> 00:06:44,000
Bene, possumus valde facilius invenire summam minimam et maximum valores.

130
00:06:44,000 --> 00:06:46,000
Invenientur valores minimi sinistrum semper victurus

131
00:06:46,000 --> 00:06:48,000
donec non sunt plures nodorum ad visitandum.

132
00:06:48,000 --> 00:06:53,000
E invenire ius summum habere ad occasum sicut unum simpliciter.

133
00:06:54,000 --> 00:06:56,000
>> Nullo alio numero non minimum vel maximum

134
00:06:56,000 --> 00:06:58,000
est sicut facilis.

135
00:06:58,000 --> 00:07:00,000
LXXXIX dicimus numero quaeritis.

136
00:07:00,000 --> 00:07:03,000
Solum concedimus reprehendo valorem cuiusque node et vado ad laevam, seu dexteram,

137
00:07:03,000 --> 00:07:06,000
node prout major est vel minor vis

138
00:07:06,000 --> 00:07:08,000
hunc quaeritis.

139
00:07:08,000 --> 00:07:11,000
Ita ut radix amet XIII, videmus LXXXIX maius

140
00:07:11,000 --> 00:07:13,000
Sic dextram.

141
00:07:13,000 --> 00:07:16,000
Nodi enim videmus XXXIV, ite dextram.

142
00:07:16,000 --> 00:07:20,000
LXXXIX adhuc major quam LV, ita et nos persevéret euntes ad dextrum.

143
00:07:20,000 --> 00:07:24,000
Nodi igitur in valore ascendit ad sinistram et CXLIV.

144
00:07:24,000 --> 00:07:26,000
Ecce adiacet LXXXIX.

145
00:07:26,000 --> 00:07:31,000
>> Aliud, quod nos can operor est procer sicco totus numeri per peractas inorder traversal.

146
00:07:31,000 --> 00:07:35,000
An inorder traversal significat ut procer omnia ex in sinistro subtree

147
00:07:35,000 --> 00:07:37,000
secuutus per excudendi, nodi se

148
00:07:37,000 --> 00:07:40,000
et deinde sequitur excudendi, omnia ex in dextro subtree.

149
00:07:40,000 --> 00:07:43,000
Pro exemplo, lets accipere nostri ventus binariae search arbor

150
00:07:43,000 --> 00:07:46,000
procer ex numeri in sorted ordinem.

151
00:07:46,000 --> 00:07:49,000
XIII ad radicem initio, priusquam typis imprimantur XIII de nobis

152
00:07:49,000 --> 00:07:51,000
omnia in sinistro subtree.

153
00:07:51,000 --> 00:07:55,000
Sic itur ad V. Adhuc altius, sinistrum maxime invenitur in ligno usque ad nodum;

154
00:07:55,000 --> 00:07:57,000
quae nulla est,.

155
00:07:57,000 --> 00:08:00,000
Post printing nulla, supra repetere usque ad I et procer ut foras.

156
00:08:00,000 --> 00:08:03,000
Tum dextram subtree est II, ex procer.

157
00:08:03,000 --> 00:08:05,000
Iam ut nos 'perfectus cum illa subtree,

158
00:08:05,000 --> 00:08:07,000
III procer ut revertar ad illud.

159
00:08:07,000 --> 00:08:11,000
Exsequenti tergum sursum, nos imprimendi V et tunc VIII.

160
00:08:11,000 --> 00:08:13,000
Iam ut nos expleverint totius reliquit subtree,

161
00:08:13,000 --> 00:08:17,000
nos can procer sicco XIII et satus opus in dextro subtree.

162
00:08:17,000 --> 00:08:21,000
Nos suspicamini usque ad XXXIV, sed ante printing XXXIV habemus ut procer de sinistro suo subtree.

163
00:08:21,000 --> 00:08:27,000
Ita et nos procer ex XXI: deinde nos adepto ut procer ex XXXIV et visita ius suum subtree.

164
00:08:27,000 --> 00:08:31,000
Quia LV non habet sinistram subtree, nos procer eum, et pergens ad ius suum subtree.

165
00:08:31,000 --> 00:08:36,000
CXLIV habet sinistram subtree, et sic procer sicco LXXXIX, quam sequitur CXLIV,

166
00:08:36,000 --> 00:08:39,000
et tandem vox-maxime nodum CCXXXIII.

167
00:08:39,000 --> 00:08:44,000
En cuncta ex ordine ab imo ad summum numeri impressis.

168
00:08:44,000 --> 00:08:47,000
>> Tam molestum est secundum appositionem in ligno.

169
00:08:47,000 --> 00:08:51,000
Quidquid habere possumus efficio est planto certus ut sequimur III binariae search arbor proprietates

170
00:08:51,000 --> 00:08:53,000
et tunc inserere valor ubi est spatium.

171
00:08:53,000 --> 00:08:55,000
VII inserere velimus dicere, pretium sit amet.

172
00:08:55,000 --> 00:08:58,000
Minus enim XIII VII, transimus ad sinistram.

173
00:08:58,000 --> 00:09:01,000
Sed maior est V sic transire ad dextrum.

174
00:09:01,000 --> 00:09:04,000
Utpote suus 'minus quam VIII et VIII est folium node, additur VII ad sinistram puer VIII.

175
00:09:04,000 --> 00:09:09,000
Voila! Weve 'added a numerus nostris binariae search arbore.

176
00:09:09,000 --> 00:09:12,000
>> Si adiungamus quae melius res posse delere.

177
00:09:12,000 --> 00:09:14,000
Infeliciter pro nobis, deleting est parum aliquantulus magis complicated -

178
00:09:14,000 --> 00:09:16,000
Ne multa, exigua.

179
00:09:16,000 --> 00:09:18,000
III missionum considerandum est aliud

180
00:09:18,000 --> 00:09:21,000
quando deleting elementa ex binariae search arboribus.

181
00:09:21,000 --> 00:09:24,000
Primo folio nodi facilis est casus elementum.

182
00:09:24,000 --> 00:09:27,000
Hic cum rem penitus delere et desere eam.

183
00:09:27,000 --> 00:09:30,000
Iustus volo ut delete VII dicimus accedunt.

184
00:09:30,000 --> 00:09:34,000
Velimus, nihil aliud invenio, cursus et Vestibulum enim.

185
00:09:35,000 --> 00:09:37,000
Postero est casus, si nodi habet nisi tantum I parvulus.

186
00:09:37,000 --> 00:09:40,000
Hic non proident nodo ad primum quidem nos

187
00:09:40,000 --> 00:09:42,000
continuaverat, subtree quod nunc reliquit ORBUS

188
00:09:42,000 --> 00:09:44,000
ad parente node nos iustus delevit.

189
00:09:44,000 --> 00:09:47,000
Dicunt, nos volo ut delete III a nostris arbore.

190
00:09:47,000 --> 00:09:50,000
Node illa pars sumatur, et coniunge ad puerum parens nodi.

191
00:09:50,000 --> 00:09:54,000
Hic iam sumus I ad V attachiandis.

192
00:09:54,000 --> 00:09:57,000
Is officina sine forsit quia scimus, secundum binariae search arbor proprietas,

193
00:09:57,000 --> 00:10:01,000
III, in sinistra vero omne minus V subtree.

194
00:10:01,000 --> 00:10:05,000
Iam ut III scriptor subtree sumitur cura, possumus delete is.

195
00:10:05,000 --> 00:10:08,000
Tertia et ultima causa est multiplex.

196
00:10:08,000 --> 00:10:11,000
Cum volumus fit nodo habet II filios turpis.

197
00:10:11,000 --> 00:10:15,000
Ad hoc quod nodi proximi prius quaerendum vis maxima,

198
00:10:15,000 --> 00:10:18,000
PERMUTO duo, et tunc delete node inquisita.

199
00:10:18,000 --> 00:10:22,000
Animadverto node quod habet postero maxima valorem non potest habere II filios ipsa

200
00:10:22,000 --> 00:10:26,000
quia sinistris eius Infantem futurum esse melius candidatus sequenti enim maxima.

201
00:10:26,000 --> 00:10:30,000
Ergo, supprimendi A nodum cum II filii recidit permutando of II nodorum,

202
00:10:30,000 --> 00:10:33,000
Deletis autem tractatur I et II normis praedictis.

203
00:10:33,000 --> 00:10:37,000
Nam tellus velimus dicere quod sit radix nodo XIII.

204
00:10:37,000 --> 00:10:39,000
Tunc primum maximas agimus pretium invenimus arborem

205
00:10:39,000 --> 00:10:41,000
quod hic est XXI.

206
00:10:41,000 --> 00:10:46,000
Igitur nos PERMUTO in II nodorum, faciens XIII folium XXI centralis group node.

207
00:10:46,000 --> 00:10:49,000
Autem possumus simpliciter delete XIII.

208
00:10:50,000 --> 00:10:53,000
>> Sicut allegati maturius, possibiles sunt plures vias ad validum binariae search arbore.

209
00:10:53,000 --> 00:10:56,000
Lorem nos aliis sunt deteriora.

210
00:10:56,000 --> 00:10:59,000
Pro exemplo, accidit quando construimus binarii search arbor

211
00:10:59,000 --> 00:11:01,000
a sorted list numeri?

212
00:11:01,000 --> 00:11:04,000
Omnes numeros es iustus additae ad dexteram ad quemlibet passum.

213
00:11:04,000 --> 00:11:06,000
Cum volumus quaerere plura,

214
00:11:06,000 --> 00:11:08,000
sed respice ad dexteram habemus optiones quolibet gradu.

215
00:11:08,000 --> 00:11:11,000
Hoc est non melius, quam linearibus search omnino.

216
00:11:11,000 --> 00:11:13,000
Licet non operient huc alia plura complexa,

217
00:11:13,000 --> 00:11:16,000
Mauris fac structurae non habet.

218
00:11:16,000 --> 00:11:18,000
Sed ne hoc fieri possit uno simplici

219
00:11:18,000 --> 00:11:21,000
ut iustus fortuite shuffle input valores.

220
00:11:21,000 --> 00:11:26,000
Suus 'altus uerisimile ut fortuitis forte lentis list numerorum est sorted.

221
00:11:26,000 --> 00:11:29,000
Hoc si ita res moram non casinos diu.

222
00:11:29,000 --> 00:11:31,000
>> Ibi te est.

223
00:11:31,000 --> 00:11:34,000
Nunc vos scire de binariae indagando et binariae search arboribus.

224
00:11:34,000 --> 00:11:36,000
Im 'Patrick Schmid, et hoc est CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
Unum obvious modo, ad lustrandum list a ... [custodite]

227
00:11:43,000 --> 00:11:46,000
... Numerus of items ... vidi,

228
00:11:46,000 --> 00:11:50,000
[Ridet]

229
00:11:50,000 --> 00:11:55,000
... Stipes nodum CCXXXIV ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Quod erat -