>> ROB Bowden: Saluton, mi estas Rob.
Kiel ni dungi duuma serĉo?
Ni ekscias.
Do atentu, ke tiu serĉo ni iras apliki rekursie.
Vi povus ankaŭ apliki duuma serĉo ripete, do se vi faris tion,
tio estas perfekte bone.
>> Nun unue, ni memoru, kion la parametroj por serĉo celas esti.
Tie, ni vidas int valoro, kiu estas supozitaj esti la valoro de la uzanto estas
serĉi.
Ni vidas la int valoroj tabelo, kiu estas la tabelo en kiu ni estas
serĉas valoron.
Kaj ni vidos int n, kiu estas la longo de nia tabelo.
>> Nun, unua afero unue.
Ni kontrolu se n egalas 0, en tiaokaze ni revenos falsaj.
Tio nur diras, se ni havas malplenan tabelo, valoro estas klare ne en
malplena tabelo, do ni povas reveni falsaj.
>> Nun, ni efektive deziras fari la duuma search parto de duuma serĉo.
Do, ni volas trovi la mezo ero de tiu tabelo.
Tie, ni diru mezo egalas n dividita per 2, ekde la meza elemento estas
tuj estos la longeco de nia tabelo dividite per 2.
Nun ni iras por kontroli, cxu la meza elemento egalas la valoro ni estas
serĉi.
Do se valoroj mezo egalas valoro, ni povas reveni vera ekde ni trovis la
valoron en nia tabelo.
>> Sed se tio ne estis vera, nun Ni bezonas fari la rekursiaj
ŝtupo de duuma serĉo.
Ni bezonas esplori ĉu al la restis el la tabelo aŭ al la
meze de la tabelo.
Do jen, ni diru, se taksas je duono estas malpli ol valoro, kiu signifas, ke valoro
estis pli granda, ol la meza de la tabelo.
Do valoro devas esti al la rajto de la elemento, ke ni nur rigardis.
>> Do jen, ni iras al serĉu rekursie.
Kaj ni vidos rigardi kion ni pasante al ĉi tio en sekundo.
Sed ni tuj serĉi la Dekstre de la meza elemento.
Kaj en la alia kazo, tio signifas ke valoro estis malpli ol la duono de la
tabelo, kaj tial ni iras sercxi maldekstren.
Nun maldekstren tuj estos iom pli facile rigardu.
Do, ni vidas ĉi tie ke ni estas rekursie nomante serĉo kie la unua
argumento estas, denove, la valoro Ni serĉas super.
La dua argumento tuj estos la tabelo, ke ni estis serĉanta super.
Kaj la lasta elemento nun estas meza.
Memoru la lastan parametron estas nia int n, do tio estas la longo de nia tabelo.
>> En la rekursia alvoko por esplori, ni estas nun dirante, ke la longeco de la
tabelo estas meza.
Do, se nia tabelo estis de grandeco 20 kaj ni esploris ĉe indeksa 10, ekde mezo estas
20 dividite per 2, tio signifas ke ni estas pasante 10 kiel la nova
longeco de nia tabelo.
Memoru, ke kiam vi havas tabelo de longo 10, kiu signifas la valida
elementoj estas en indeksoj 0 tra 9.
Do tiu estas ekzakte kion ni volas specifi nia ĝisdatigita tabelo - maldekstre
tabelo el la meza elemento.
>> Do, rigardante dekstren estas iom pli malfacila.
Nun unue, ni konsideru la longo de la tabelo al la rajto de la
meza elemento.
Do, se nia tabelo estis de amplekso n, tiam la nova tabelo estos de amplekso n minus
mezo minus 1.
Do, ni pensu pri n minus mezo.
>> Denove, se la tabelo estis de amplekso 20 kaj Ni dividu per 2 al preni la mezo,
do la meza estas 10, tiam n minus mezo tuj donas al ni 10, do 10
elementojn al la rajto de mezo.
Sed ni ankaŭ havas ĉi tiun minus 1, pro tio ni ne volas
inkluzivas la mezo mem.
Do n minus mezo minus 1 donas al ni la totala nombro de elementoj al la dekstra
el la mezo indekso en la tabelo.
>> Nun ĉi tie, memoru, ke la meza parametro estas la valoroj tabelo.
Do jen, ni pasas al ĝisdatigita valoroj tabelo.
Ĉi valoroj plus duono plus 1 estas reale dirante rekursie voki
search, pasante en nova tabelo, kie ke novaj tabelo startas en la mezo
plus unu de niaj originalaj valoroj tabelo.
>> Alternativa sintakso por tio, nun ke vi jam komencis vidi montriloj, estas
ampersand valoroj mezo plus 1.
Do, kaptu la adreso de la mezo plus unu elemento de valoroj.
>> Nun, se vi ne estis komforta modifi tabelon kiel ke, vi
povus ankaux esti implementado ĉi uzante rekursia helpanton funkcio, kie
ke helpanto funkcio prenas pli argumentojn.
Do anstataŭ preni nur la valoro, la tabelo, kaj la grandeco de la tabelo,
helpanto funkcio povus preni pli argumentoj, inkluzive de la suba indekso
ke vi zorgas pri la tabelo kaj la supra indico kiu vi zorgas
pri la tabelo.
>> Kaj tiel konservanta trako de ambaŭ la malsupra indekso kaj la supra indico, vi ne
bezonas iam modifi la originalaj valoroj tabelo.
Vi povas simple daŭre uzi la valoroj tabelo.
Sed ĉi tie, rimarki ke ni ne bezonas helpantojn funkcii kiel longa kiel ni estas
volante modifi la originalan valorojn tabelo.
Ni pretas Iam en ĝisdatigita valoroj.
>> Nun, ni ne povas duuma serĉo super tabelo, kiu estas Unsorted.
Do, ni ricevas tiun ordo ekstere.
Nun, rimarki ke varo estas pasintaj du parametroj int valoroj, kiuj estas la
tabelo, ke ni ordig kaj int n, kiu estas la longo de la tabelo, kiu
ni ordig.
Do, ĉi tie ni volas apliki ordiga algoritmo
ke estas o de n kvadratoj.
Vi povus elekti bobelo varon, elekto varon, aŭ inserción varon, aŭ
iu alia speco ke ni havas ne vidis en la klaso.
Sed cxi tie, ni iras al uzi selektado varo.
>> Do, ni iras al persisti super la tuta tabelo.
Nu, jen ni vidas ke ni estas ripetanta de 0 al n minus 1.
Kial ne la tuta vojo ĝis n?
Nu, se ni jam ordigitaj la unua n minus 1 elementoj, tiam la
lasta elemento kio devas jam esti en la ĝusta loko, do ordig super
en la tuta tabelo.
>> Nu, memoru, kiamaniere selektado speco funkcias.
Ni tuj iras trans la tuta tabelo serĉante la minimuma valoro en
la tabelo kaj bastono ke en la komenco.
Tiam ni tuj iru super la tuta tabelo denove serĉas la dua
plej malgranda ero, kaj bastono ke en la dua pozicio en la
tabelo, kaj tiel plu.
Do, tio estas kion tiu faras.
>> Tie, ni vidas ke ni estas opcio la aktuala minimuma
valoro al la i-a indekso.
Do en la unua ripeto, ni iras konsideri la minimuman valoron por esti
la komencon de nia tabelo.
Poste, ni iras al persisti super la restaĵon de la tabelo, kontrolanta al
vidi se nenia elementoj pli malgrandaj ol kiu ni aktuale
konsiderante la minimumo.
>> Do jen, valoroj j plus unu - tio estas malpli ol kion ni estas aktuale
konsiderante la minimumo.
Tiam ni iras por ĝisdatigi kio Ni pensas estas la minimumo por
indekso j plus 1.
Do, faru, ke tra la tuta tabelo, kaj post tio por buklo, minimuma
devus esti la minimuma ero de la i-a pozicio en la tabelo.
>> Iam ni havas tion, ni povas interŝanĝi la minimuma valoro en la i-a pozicio
en la tabelo.
Do tiu estas nur normo swap.
Ni stokas en portempa valoro - la i-a valoro en la tabelo -
meti en la i-a valoro en la tabelo la minimuma valoro kiu apartenas tie,
kaj do gardi reen en kie la aktuala minimuma valoro kutimis esti la
i-a valoro en la tabelo, do ke ni ne perdos.
>> Do, kiu daŭrigas en la sekva ripeto.
Ni komencos serĉi la duan minimuma valoro kaj enmeti tion en la
dua pozicio.
Sur la tria ripeta, ni devos serĉi la tria minimuma valoro kaj insert
ke en la tria pozicio, kaj tial plu ĝis ni havos ordo tabelo.
Mia nomo estas Rob, kaj ĉi Estis elekto varo.