>> [MUZIKO Ludanta]
>> ZAMYLA CHAN: La unua afero, vi eble avizo pri trovaĵo estas ke ni jam
esti skribita kodo por ni.
Tio nomiĝas distribuo kodo.
Do ni ne simple skribi nian propran kodigi de nulo plu.
Pli ĝuste, ni plenigante en la malplenaj en kelkaj pre-ekzistanta kodo.
>> La find.c programo stimulanta por nombroj plenigi la fojnamaso, esploras la
fojnamaso por uzanto donita kudrilo, kaj ĝi faras tion per la alvoko varo kaj
search, funkcioj difinitaj en helpers.c.
Do find.c estas skribita jam.
Via tasko estas skribi helpantoj.
>> Do, kion ni faras?
Ni efektivigo du funkcioj.
Search, kiuj revenas vera se valoro troviĝas en la fojnamaso, revenante
malvera se la valoro estas ne en la fojnamaso.
Kaj tiam ni ankaŭ efektivigo speco kiuj ordigas la tabelo nomata valoroj.
>> Do ni pritrakti serĉo.
Serĉu aktuale implementado kiel lineara serĉo, sed vi povas fari multe
pli bone ol tio.
Lineara serĉo implementado en O de n tempon, kio estas sufiĉe malrapidaj.
Kvankam, ĝi povas serĉi neniu listo donita al gxi.
Via laboro estas efektivigi duuma serĉo, kiu kuras tempo O de log n.
Tio estas sufiĉe rapida.
>> Sed tie estas estipulación.
Duuma serĉo povas nur serĉi per antaŭ-ordo listoj.
Kial estas tiel?
>> Bone ni rigardu ekzemplon.
Donita aro de valoroj, la fojnamaso, Ni tuj rigardos
por kudrilo.
Kaj en ĉi tiu ekzemplo, la entjera tri.
La vojo kiu duuma serĉo laboras estas, ke ni komparu la meza valoro de
la tabelo al la kudrilon, multe ŝatas kiel Ni malfermis phonebook al la mezo
paĝo en semajno nulo.
>> Do post komparante la meza valoro al la kudrilon, vi povas forĵeti nek la
maldekstra aŭ la dekstra duono de la tabelo por premita viajn limojn.
En ĉi tiu kazo, ekde tri, nia kudrilo, estas malpli ol 10, la meza valoro, la
dekstra baro povas malaltiĝi.
Sed provu fari viajn limojn kiel firme kiel eble.
Se la meza valoro ne estas la kudrilon, tiam vi scias ke vi ne bezonas
inkluzivi ĝin en via serĉo.
Do vi pravas binditaj povas streĉi la search limojn nur ete pli,
kaj tiel plu kaj tiel plu ĝis vi trovos vian kudrilo.
>> Do kion signifas la _pseudocode_ aspekti?
Nu, dum ni ankoraŭ rigardas tra la listo kaj ankoraŭ havas elementojn por
enrigardi, ni prenu la mezo de la listo, kaj kompari ke meza valoro al
nia kudrilo.
Se ili estas egalaj, tiam tio signifas ke ni jam trovis la kudrilon kaj ni povas
return true.
>> Alie, se la kudrilo estas malpli ol la meza valoro, do tio signifas ke ni
povas forĵeti la dekstra duono, kaj nur serĉu la maldekstra flanko de la tabelo.
Alie ni esploru la dekstra flanko de la tabelo.
Kaj fine, se vi ne havas neniu pli elementoj forlasis por serĉi sed vi
ne trovis viajn kudrilo tamen, tiam vi redoni malvera ĉar la kudrilo
definitive ne estas en la fojnamaso.
>> Nun neta afero pri ĉi _pseudocode_ en duuma serĉo estas ke ĝi povas esti
interpretita kiel ĉu ripeta aŭ rekursiaj efektivigo.
Do ĝi estus rekursie se vi nomas la serĉo funkcion ene de la serĉo
funkcii sur ĉu la duonon de la tabelo.
Ni devos kovri rekursio iom poste en la Certe, sed vi scias ke ŝi estas
opcion se vi ŝatus provi.
>> Nun ni rigardu varo.
Ordigi prenas tabelo kaj la entjero n, kiu estas la grandeco de la tabelo.
Nun ekzistas diversaj malsamaj tipoj de varoj, kaj vi povas rigardi iun
shorts por donu kaj klarigoj.
La reveno tipo por nia speco funkcio estas malplena.
Do tio signifas ke ni ne tuj reveni ajna tabelo de varo.
Ni efektive tuj ŝanĝos la tre tabelo kiu pasis al ni.
>> Kaj tio estas ebla ĉar arrays estas preteriris referenco en C. Nun ni
vidi pli pri tio poste, sed la esenca diferenco inter forpaso
en iu kiel entjero kaj forpaso en tabelo, estas, ke kiam vi
Iam en entjero, C estas ĝuste tuj fari kopion de tiu entjero migru
ĝin al la funkcio.
La originala variablo ne estos ŝanĝitaj Tuj la funkcio estas finita.
Kun tabelo, aliflanke, estas Ne tuj fari kopion, kaj vi ricevos
reale esti redaktado de la tre batalarangxis sin.
>> Do unu tipo de varo estas la elekto varo.
La selektado speco funkcias per startanta je la komenco, kaj tiam vi ankaŭ persisti
super kaj trovu la plej malgranda ero.
Kaj tiam vi interŝanĝas, ke malgranda ero kun la unua.
Kaj tiam vi movas al la dua ero , Trovu la sekva pli malgranda
elemento, kaj do interŝanĝas ke kun la dua ero en la tabelo ĉar
La unua ero jam ordo.
Kaj tiel do vi daŭrigas por ĉiu elemento en la identigi la plej malgranda
valoro kaj interŝanĝi ĝin.
>> Por mi egalas 0, la unua elemento al n minus 1, vi tuj kompari
ĉiun sekvanta valoro post tio kaj trovu la indekso de la minimuman valoron.
Kiam vi trovos la minimuman valoron indekso, vi povas interŝanĝi ke valoro de tabelo
minimumo kaj batalarangxis I.
>> Alia tipo de varo kiun vi povas apliki estas bobelo varo.
Do bobelo speco ripetas super la listo komparante najbaraj elementoj kaj
interŝanĝi la elementoj kiuj estas en la malĝusta ordo.
Kaj tiamaniere, la plej granda ero volo veziko ĝis la fino.
Kaj la listo estas ordigita unufoje ne plu eroj estis ŝanĝitaj.
>> Do tiuj estas du ekzemploj de la varo algoritmoj kiuj povas apliki por
la trovaĵo programo.
Kiam vi finos varon, kaj vi havas farita serĉo, vi finis.
Mia nomo estas Zamyla, kaj ĉi tiu estas CS50.
>> [MUZIKO Ludanta]