>> 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ŭ apliki varon, 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 ol tio.
Lineara serĉo implementado en O de n tempo, kio estas sufiĉe malrapida, kvankam ĝi
povas serĉi ajna 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?
Nu, ni rigardu ekzemplon.
Donita aro de valoroj, la fojnamaso, Ni tuj rigardos
por kudrilo, kaj en tiu Ekzemple, la entjero 3.
>> 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 telefono libron al la mezo
paĝo en Semajnon 0.
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 3, nia nadlo, 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 via dekstra ligitaj povas streĉi la search limojn nur ete pli,
kaj tiel plu kaj tiel plu, ĝis vi trovos vian kudrilo.
>> Do, kion faras la pseŭda kodo aspekti?
Nu, dum ni ankoraŭ rigardas tra la listo kaj ankoraŭ havas
elementoj enrigardi, ni prenu la mezo el 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 justa 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 reiros falsaj.
Ĉar la kudrilo definitive ne estas en la fojnamaso.
>> Nun, unu neta afero pri tiu pseŭda kodo en duuma serĉo estas ke ĝi ne 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 kurso.
Sed sciu, ke tio estas eblo se vi ŝatus provi.