[Powered by Google Translate] [Binariae Quaero]
[Patrick Schmid - Harvard University]
[Hoc est CS50. - CS50.TV]
>> Si ego dedi vobis a album of Disney character nomina in ordinem alphabeti
et interrogavit vobis invenire Mickey Mus,
quomodo vis ire circa haec facis
Unum obvious modo, ad lustrandum list ab initio
et coercere omne nomen, ut videret si suus 'Mickey.
Sed habes Aladdin Alicia Arihel et cetera,
mox inde in fronte intellego te non lectus utilem.
Bene, fortasse retro a fine facientes initium elit.
Nunc legistis Tarzan, CONSUO Nix White, et sic porro.
Tamen ut non videatur sicut eam melius.
>> Bene, quod aliter est de ea re conari posse contrahere
Tu vide indicem nominum.
Cum scias quod in litteras,
aspicite in medio possis indice nominum
nisi prius aut posterius nomen reprehendo amet dolore.
In nibh nibh intuentes
youd 'animadverto ut M pro Mickey venit post J pro Jasmine,
sic youd simpliciter ignoratorum primoris dimidium of album.
Tunc youd 'forsit, respice ad verticem ultima columna
et vide quia incipit cum Rapunzel.
Mickey venit ante Rapunzel, vultusface, amo nos neglegat ultima columna pariter.
Exsequenti quaero rationem belli, youll 'velociter animadverto ut Mickey
Prima pars cetera nomina in albo
et tandem inveniet Mickey latitantes inter Merlini et Minnie.
>> Quid vos iustus faciebat basically binariae search.
Ut hoc nomen importat, fungatur eius indagando militarium in binarii materia.
Quid hoc sibi vult?
Bene, dato a album of sorted items, binariae search algorithm facit binariae decisionem -
laeva sive dextera, majus aut minus, prius et posterius alphabetically - in singulis.
Hic jam quaeritur nomen algorithm it,
Intueamur ergo aliud, sed cum digestus indicem numerorum.
Dicunt, nos exspectantes numerus CXLIV in hoc album of sorted numerorum.
Sicut prius est invenire numerum media -
quo in casu XIII - XIII et minus quam si CXLIV.
XIII maius est evidenter eo quod potest ignorare, quod omnia fere XIII
et justum incumbo in residuam medietatem.
Cum iam rebus par ad reliquum
penitus media elige turba prope est.
LV hic velimus.
LXXXIX elegit tam facile possimus.
Okay. Item, maior est CXLIV LV ita dextram.
Fortunate pro nobis, sequenti numero medio est CXLIV,
hunc quaeritis.
Sic ut inveniret CXLIV usura a binariae search, sumus invenire poteritis, hoc solum in III steps.
Si nos usi fuissent linearibus search, esset ceperint nobis XII steps.
Adeo ut, cum quaeritur ratio sumpta ex rerum copia
inspiciendum est ad quemlibet passum est item quaerens inveniet
acta res in numero fere numero.
II His exempla vidi, lets 'inspice
quidam pseudocode pro recursive functio, ut effectum adducit binariae search.
Summo amet videmus quod id quod pertinet ad quaerendum IV argumentorum
clavis aciem min et Max.
Quaeratur quot sit amet, ut in priore exemplo CXLIV.
Indicem numerorum bellum quaerimus.
Min et max sunt indices summam minimam et maximum positionum
ut nos es currently aspiciendo.
Cum imus min velit eget nulla erit repugnantia acies Max.
Sicut et nos arta search descendit, nos mos update min et max
Etiam ut elit rhoncus respiciens ad iustitiam
>> Lets skip ad interesting pars prima.
Nos invenire primum est medium,
tum, quod medium inter maximum et minimum qui de acie adhuc considerare.
Videamus quae deinde sedes valorem medium locum
et si quaeratur numerus minor est clavis.
Si numerus ad minorem locum,
igitur maior sit amet sinistra numerorum dispositione.
Sic possumus appellare, binariae quaero muneris iterum,
tamen is vicis adaequationis ad min et max parametris legere iustus dimidiae
Sicut pretium et paribus maior existit.
Rursus, si minor numero amet nunc in medium agmen
et sinistram volumus ignorare quod omnibus numeris auxerunt.
Rursus, vocamus binariae search sed hoc tempus cum range of min et max Updated
ad includantur dimidiae partis inferioris.
Si valor ad current mediocritatem in, in aciem nec est
nec minus maiora amet Ergo aequalis sit amet.
Et sic possumus simpliciter redire current mediocritatem index, et nos 'perfectus.
Denique hoc erit quod sequatur numerus
quaerimus non numerorum seriem in actu.
Maxime si quaeratur iugis index
semper quam minimum excessisse diximus Id.
Cum numerus non erat in input apparatu, revertamur -1
Etiam non inveniebatur.
>> Idque ut dictum algorithm operari
elenchus, numerorum habet sorted.
In aliis verbis, tantum modo cogitatione possumus invenire CXLIV usura binariae search
si ab imo ad summum omnibus numeris ordinantur.
Non hoc, non excludit partem numeri possent utraque gradum.
Sic habemus II bene.
Aut nos potest capere an Unsorted album quod exstat illud coram usura binariae search,
aut possumus efficere ut nos commoda augere numerum numerorum multitudo est.
Sic, pro voluptua iustus cum habeamus ut investigaret,
cur non servant list sorted omni tempore?
>> Unum via ut servo a album numerorum sorted dum simul præbens
unum addere vel movere numerorum ex is album
est per usura aliquid dicitur binariae search arbore.
A binariae search arbor est notitia revoluta quae habet III proprietates.
Primo, sinistro subtree alicuius node continet tantummodo valores, qui sunt minus quam
aut aequalis node scriptor valorem.
Secundo, ius subtree of a node tantum continet valores, qui sunt maiores quam
aut aequalis node scriptor valorem.
Denique nodos omnis et dextra subtrees
sunt etiam binariae search arboribus.
Intueamur exemplum iisdem numeris supra usi sumus.
Enim vobis eorum qui numquam vidimus a computer scientia arbor ante,
permissum mihi incoeperunt per dico vos ut a computer scientia arbor deorsum.
Yes, dissimiles arbores soletis,
radix arboris scientiae eu superius,
imo et folia.
Singulis capsellam dicitur node, et nodorum sunt connexae ad invicem marginibus.
Nodi igitur est huius arboris radix XIII quanti valoris,
quae habet II filios nodis cum valores V et XXXIV.
Solum est lignum formatum in subtree ordo universi visione arboris.
>> Pro exemplo, sinistro subtree de node III est arbor creata a nodorum 0, I, et II.
Si igitur inquisitio passiones binarii redire ad arborem
node convenit inter omnes arbor videmus in III proprietatibus, scilicet
sinistram subtree solum continet valores, qui sunt minus quam aut aequalis node scriptor valorem;
ius subtree omnium nodorum
tantum continet valores, qui sunt maiores quam aut aequalis node scriptor valorem; et
utrumque dextra laevaque subtrees omnium nodorum quoque sunt binariae search arboribus.
Licet hoc arbor spectat diversis, hoc validum est, binariae search arbor
profectus eadem numero.
Adeo ut multa modis efficere potest ut
validum binariae search arbor ex his numerorum.
Age, eamus ad nos prior crearetur.
Quid ergo faciemus istis ligna
Bene, possumus valde facilius invenire summam minimam et maximum valores.
Invenientur valores minimi sinistrum semper victurus
donec non sunt plures nodorum ad visitandum.
E invenire ius summum habere ad occasum sicut unum simpliciter.
>> Nullo alio numero non minimum vel maximum
est sicut facilis.
LXXXIX dicimus numero quaeritis.
Solum concedimus reprehendo valorem cuiusque node et vado ad laevam, seu dexteram,
node prout major est vel minor vis
hunc quaeritis.
Ita ut radix amet XIII, videmus LXXXIX maius
Sic dextram.
Nodi enim videmus XXXIV, ite dextram.
LXXXIX adhuc major quam LV, ita et nos persevéret euntes ad dextrum.
Nodi igitur in valore ascendit ad sinistram et CXLIV.
Ecce adiacet LXXXIX.
>> Aliud, quod nos can operor est procer sicco totus numeri per peractas inorder traversal.
An inorder traversal significat ut procer omnia ex in sinistro subtree
secuutus per excudendi, nodi se
et deinde sequitur excudendi, omnia ex in dextro subtree.
Pro exemplo, lets accipere nostri ventus binariae search arbor
procer ex numeri in sorted ordinem.
XIII ad radicem initio, priusquam typis imprimantur XIII de nobis
omnia in sinistro subtree.
Sic itur ad V. Adhuc altius, sinistrum maxime invenitur in ligno usque ad nodum;
quae nulla est,.
Post printing nulla, supra repetere usque ad I et procer ut foras.
Tum dextram subtree est II, ex procer.
Iam ut nos 'perfectus cum illa subtree,
III procer ut revertar ad illud.
Exsequenti tergum sursum, nos imprimendi V et tunc VIII.
Iam ut nos expleverint totius reliquit subtree,
nos can procer sicco XIII et satus opus in dextro subtree.
Nos suspicamini usque ad XXXIV, sed ante printing XXXIV habemus ut procer de sinistro suo subtree.
Ita et nos procer ex XXI: deinde nos adepto ut procer ex XXXIV et visita ius suum subtree.
Quia LV non habet sinistram subtree, nos procer eum, et pergens ad ius suum subtree.
CXLIV habet sinistram subtree, et sic procer sicco LXXXIX, quam sequitur CXLIV,
et tandem vox-maxime nodum CCXXXIII.
En cuncta ex ordine ab imo ad summum numeri impressis.
>> Tam molestum est secundum appositionem in ligno.
Quidquid habere possumus efficio est planto certus ut sequimur III binariae search arbor proprietates
et tunc inserere valor ubi est spatium.
VII inserere velimus dicere, pretium sit amet.
Minus enim XIII VII, transimus ad sinistram.
Sed maior est V sic transire ad dextrum.
Utpote suus 'minus quam VIII et VIII est folium node, additur VII ad sinistram puer VIII.
Voila! Weve 'added a numerus nostris binariae search arbore.
>> Si adiungamus quae melius res posse delere.
Infeliciter pro nobis, deleting est parum aliquantulus magis complicated -
Ne multa, exigua.
III missionum considerandum est aliud
quando deleting elementa ex binariae search arboribus.
Primo folio nodi facilis est casus elementum.
Hic cum rem penitus delere et desere eam.
Iustus volo ut delete VII dicimus accedunt.
Velimus, nihil aliud invenio, cursus et Vestibulum enim.
Postero est casus, si nodi habet nisi tantum I parvulus.
Hic non proident nodo ad primum quidem nos
continuaverat, subtree quod nunc reliquit ORBUS
ad parente node nos iustus delevit.
Dicunt, nos volo ut delete III a nostris arbore.
Node illa pars sumatur, et coniunge ad puerum parens nodi.
Hic iam sumus I ad V attachiandis.
Is officina sine forsit quia scimus, secundum binariae search arbor proprietas,
III, in sinistra vero omne minus V subtree.
Iam ut III scriptor subtree sumitur cura, possumus delete is.
Tertia et ultima causa est multiplex.
Cum volumus fit nodo habet II filios turpis.
Ad hoc quod nodi proximi prius quaerendum vis maxima,
PERMUTO duo, et tunc delete node inquisita.
Animadverto node quod habet postero maxima valorem non potest habere II filios ipsa
quia sinistris eius Infantem futurum esse melius candidatus sequenti enim maxima.
Ergo, supprimendi A nodum cum II filii recidit permutando of II nodorum,
Deletis autem tractatur I et II normis praedictis.
Nam tellus velimus dicere quod sit radix nodo XIII.
Tunc primum maximas agimus pretium invenimus arborem
quod hic est XXI.
Igitur nos PERMUTO in II nodorum, faciens XIII folium XXI centralis group node.
Autem possumus simpliciter delete XIII.
>> Sicut allegati maturius, possibiles sunt plures vias ad validum binariae search arbore.
Lorem nos aliis sunt deteriora.
Pro exemplo, accidit quando construimus binarii search arbor
a sorted list numeri?
Omnes numeros es iustus additae ad dexteram ad quemlibet passum.
Cum volumus quaerere plura,
sed respice ad dexteram habemus optiones quolibet gradu.
Hoc est non melius, quam linearibus search omnino.
Licet non operient huc alia plura complexa,
Mauris fac structurae non habet.
Sed ne hoc fieri possit uno simplici
ut iustus fortuite shuffle input valores.
Suus 'altus uerisimile ut fortuitis forte lentis list numerorum est sorted.
Hoc si ita res moram non casinos diu.
>> Ibi te est.
Nunc vos scire de binariae indagando et binariae search arboribus.
Im 'Patrick Schmid, et hoc est CS50.
[CS50.TV]
Unum obvious modo, ad lustrandum list a ... [custodite]
... Numerus of items ... vidi,
[Ridet]
... Stipes nodum CCXXXIV ... augh.
>> Yay! Quod erat -