>> ROB BOWDEN: Hi, mwen se Rob.
Ki jan nou anplwaye yon rechèch binè?
Se pou yo jwenn deyò.
Se konsa, sonje ke rechèch sa a nou pral aplike recursive.
Ou kapab tou aplike binè rechèch iterativman, kidonk si w fè sa,
sa a, se parfe amann.
>> Koulye a, premye, se pou yo sonje sa a paramèt nan rechèch yo vle di ke yo dwe.
Isit la, nou wè valè Int, ki se sipoze valè a itilizatè a se
pou chèche.
Nou wè etalaj la valè Int, ki se etalaj la nan ki nou ap
pou chèche valè.
Lè nou wè Int n, ki se longè a nan etalaj nou an.
>> Koulye a, premye bagay an premye.
Nou tcheke yo wè si n egal 0, nan ka sa a nou retounen fo.
Se jis di si nou gen yon vid etalaj, valè a se klèman pa nan yon
etalaj vid, pou nou ka retounen fo.
>> Koulye a, nou aktyèlman vle fè binè la pati rechèch la binè rechèch la.
Se konsa, nou vle jwenn mitan an eleman nan etalaj sa a.
Isit la, nou di mitan egal n divize pa 2, depi eleman nan mitan an se
pral fè longè a nan etalaj nou divize pa 2.
Koulye a, nou ap ale nan tcheke yo wè si la eleman mitan egal valè a nou ap
pou chèche.
Se konsa, si valè mitan egal valè, nou ka retounen vre depi nou te jwenn nan
valè nan etalaj nou an.
>> Men, si sa ki te pa vre, koulye a nou bezwen fè repetitif la
etap nan binè rechèch la.
Nou bezwen nan rechèch swa nan la kite nan etalaj la oswa nan la
mwayen nan etalaj la.
Se konsa, isit la, nou di si valè nan mitan an se mwens pase valè, sa vle di ke valè
te pi gwo pase mitan an nan etalaj la.
Se konsa, valè yo dwe a dwat a la eleman ki nou jis gade.
>> Se konsa, isit la, nou ap ale nan rechèch recursive.
Epitou, n ap gade nan ki sa nou ap pase sa a nan yon dezyèm fwa.
Men, nou ap ale nan rechèch la dwat Bondye ki gen eleman nan mitan.
Ak nan lòt ka a, sa vle di valè te mwens pase la nan mitan an
etalaj, e konsa nou pral nan rechèch sou bò goch la.
Koulye a, bò gòch la a pwal yon ti jan pi fasil fè yon gade nan.
Se konsa, nou wè isit la ke nou ap recursive rele rechèch kote premye a
agiman se, ankò, valè a nou ap chèche sou.
Agiman nan dezyèm a pwal nan etalaj ke nou te chache sou.
Apre sa, eleman ki sot pase a kounye a se presegondè.
Sonje dènye paramèt a se Int nou n, se konsa sa a, se longè a nan etalaj nou an.
>> Nan apèl la repetitif nan rechèch, nou kounye a ki di ke longè a nan la
etalaj se presegondè.
Se konsa, si etalaj nou an te nan gwosè 20 ak nou fouye nan endèks 10, depi mitan an se
20 divize pa 2, sa vle di nou ap pase 10 kòm nouvo a
longè nan etalaj nou an.
Sonje ke lè ou gen yon etalaj longè 10, sa vle di ki valab la
eleman yo nan endis 0 jiska 9.
Se konsa, sa a se ekzakteman ki sa nou vle presize mete ajou etalaj nou yo - bò gòch la
etalaj soti nan eleman la presegondè.
>> Se konsa, kap sou bò dwat la se yon ti jan pi difisil.
Koulye a, premye, se pou yo konsidere longè a nan etalaj la a dwat a la
mitan eleman.
Se konsa, si etalaj nou an te nan gwosè n, Lè sa a, nan nouvo etalaj yo pral nan gwosè n mwens
mwens mitan 1.
Se konsa, kite a panse a n mitan mwens.
>> Yon fwa ankò, si etalaj la yo te nan gwosè 20 ak nou divize pa 2 yo ka resevwa mitan an,
Se konsa, mitan an se 10, Lè sa a, n mwens mitan ki pral ban nou 10, Se konsa, 10
eleman sou bò dwat la nan mitan.
Men, nou menm tou nou gen mwens sa a 1, depi nou pa vle
gen ladan mitan nan tèt li.
Se konsa, n mwens mitan mwens 1 ban nou an manm kantite eleman sou bò dwat la
nan endèks la presegondè yo nan etalaj la.
>> Koulye a isit la, sonje ke lekòl presegondè a paramèt se etalaj la valè.
Se konsa, isit la, nou ap pase yon mete ajou valè etalaj.
Sa a valè plis mitan plis 1 se aktyèlman li di recursive rele
rechèch, pase nan yon nouvo etalaj, kote ke nouvo etalaj kòmanse nan mitan an
plis youn nan nou an valè etalaj orijinal la.
>> Yon sentaks lòt pou sa, kounye a ke ou te te kòmanse wè pwent, se
valè komersyal mitan plis 1.
Se konsa, gen tan pwan adrès ki nan mitan an plis yon eleman nan valè.
>> Koulye a, si ou pa t 'alèz modifye yon etalaj tankou sa yo, ou
ta ka tou te aplike sa a lè l sèvi avèk yon fonksyon k'ap vin ede repetitif, kote
ki fonksyon k'ap vin ede pran plis agiman.
Se konsa, olye pou yo pran jis valè an, nan etalaj, ak gwosè a nan etalaj la,
fonksyon an k'ap vin ede kapab pran plis agiman, ki gen ladan endèks la pi ba
ke ou ta pran swen sou nan etalaj la ak endèks la anwo ke ou pran swen
sou etalaj la.
>> Se konsa, kenbe tras nan tou de pi ba a endèks ak endèks la anwo kay la, ou pa fè sa
bezwen tout tan tout tan modifye nan valè orijinal etalaj.
Ou ka jis kontinye sèvi ak etalaj la valè.
Men, isit la, remake nou pa bezwen yon lòt moun sanble fonksyone osi lontan ke nou ap
vle modifye orijinal la valè etalaj.
Nou vle pase nan yon mete ajou valè.
>> Koulye a, nou pa kapab binè rechèch sou yon etalaj se sa ki triye.
Se konsa, kite a jwenn sa a Ranje soti.
Koulye a, remake ke sòt se sot pase yo de paramèt int valè, ki se nan
etalaj ke nou ap klasman, ak Int n, ki se longè a nan etalaj la ki
nou ap klasman.
Se konsa, isit la nou vle aplike yon algorithm Fouye
se sa ki o n okib.
Ou te kapab chwazi sòt ti wonn, seleksyon sòt, oswa ensèsyon sòt, oswa
kèk lòt sòt nou pa jwenn okenn wè nan klas la.
Men, isit la, nou ap ale nan sèvi ak sòt seleksyon an.
>> Se konsa, nou ap ale nan repňte sou etalaj la tout antye.
Oke, isit la nou wè ke nou ap iteration ki ant 0 a n mwens 1.
Poukisa nou pa tout wout la jiska n?
Bon, si nou te deja klase premye a n mwens 1 eleman, Lè sa a, nan
trè dènye eleman sa yo dwe deja ap nan plas ki kòrèk la, se konsa klasman sou
etalaj la tout antye.
>> Koulye a, sonje ki jan seleksyon sòt travay.
Nou pral ale sou etalaj la tout antye kap chèche valè minimòm lan nan
etalaj la ak baton ki nan kòmansman an.
Lè sa a, nou pral ale sou tout la etalaj ankò kap chèche dezyèm lan
pi piti eleman, ak baton ki nan yon pozisyon nan dezyèm nan la
etalaj, ak sou sa.
Se konsa, se sa ki sa a ap fè.
>> Isit la, nou ap wè ke nou ap mete minimòm aktyèl la
valè nan endèks la m-th.
Se konsa, sou iterasyon a an premye, nou pral yo konsidere valè a minimòm yo dwe
nan kòmansman an nan etalaj nou an.
Lè sa a, nou pral repňte sou la rès nan etalaj la, tcheke
wè si gen nenpòt eleman ki pi piti pase youn nan ki nou ap kounye a
konsidere minimòm la.
>> Se konsa, isit la, valè j plis yon - sa a mwens pase sa nou yo kounye a
konsidere minimòm la.
Lè sa a, nou pral mete sa nou panse se minimòm nan
endèks j plis 1.
Se konsa, fè sa atravè etalaj la an antye, ak apre sa a pou bouk, minimòm
yo ta dwe eleman minimòm-nan soti nan pozisyon nan m-th nan etalaj la.
>> Yon fwa nou genyen ki, nou ka swap la minimòm valè nan pozisyon an mwen-th
nan etalaj la.
Se konsa, sa a se jis yon swap estanda.
Nou sere nan yon valè pou yon ti tan - valè a m-th nan etalaj la -
mete nan valè a m-th nan etalaj la nan minimòm valè pou moun ki te la,
ak Lè sa a, magazen tounen antre nan kote a kounye a valè minimòm itilize yo dwe nan
valè m-th nan etalaj la, se konsa ke nou pa t 'pèdi li.
>> Se konsa, ki ap kontinye sou pwochen iterasyon la.
Nou pral kòmanse kap chèche dezyèm lan minimòm valè ak insert ki nan la
dezyèm pozisyon.
Sou twazyèm iterasyon a, nou pral gade pou valè minimòm-nan twazyèm ak insert
ki nan twazyèm pozisyon an, e konsa sou jouk nou gen yon etalaj tri.
Non mwen se Rob, ak sa a te sòt seleksyon an.