[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]