>> Rob BOWDEN: Hi, mimi nina Rob.
Je, sisi kuajiri search binary?
Hebu kujua.
Hivyo, kumbuka kwamba hii tafuta tunakwenda kutekeleza recursively.
Unaweza pia kutekeleza search binary iteratively, hivyo kama wewe alifanya hivyo,
kwamba kikamilifu faini.
>> Sasa kwanza, hebu kumbuka nini vigezo search ni maana ya kuwa.
Hapa, tunaona int thamani, ambayo ni wanatakiwa kuwa thamani user ni
ajili ya kutafuta.
Tunaona maadili int safu, ambayo ni safu ambayo tuko
kwa ajili ya kutafuta thamani.
Na tunaona int n, ambayo ni urefu wa safu yetu.
>> Sasa, jambo la kwanza kwanza.
Sisi kuangalia ili kuona kama n sawa na 0, katika kesi ambayo sisi kurudi uongo.
Hiyo tu kusema kama tuna tupu safu, thamani ni wazi si katika
safu tupu, ili tuweze kurudi uongo.
>> Sasa, sisi kweli unataka kufanya binary search sehemu ya kutafuta binary.
Kwa hiyo, tunataka kupata katikati kipengele cha safu hii.
Hapa, tunasema katikati ni sawa na n kugawanywa na 2, tangu hiki katikati ni
kwenda kuwa urefu wa safu yetu kugawanywa na 2.
Sasa tunakwenda kuangalia kuona kama hiki katikati ni sawa na thamani sisi ni
ajili ya kutafuta.
Hivyo kama maadili katikati ni sawa na thamani, sisi anaweza kurudi kweli tangu sisi kupatikana
thamani katika safu yetu.
>> Lakini kama hiyo ilikuwa si ya kweli, sasa tunahitaji kufanya kujirudia
hatua ya kutafuta binary.
Sisi haja ya kutafuta ama kushoto wa safu au kwa
katikati ya safu.
Hivyo hapa, tunasema kama maadili katikati ni chini ya thamani, hiyo ina maana thamani kwamba
ilikuwa kubwa zaidi kuliko katikati wa safu.
Hivyo thamani lazima na haki ya hiki kwamba sisi tu inaonekana katika.
>> Hivyo hapa, tunakwenda kutafuta recursively.
Na tutaangalia nini sisi ni kupita hii katika pili.
Lakini sisi ni kwenda kutafuta kwa haki ya hiki katikati.
Na katika kesi nyingine, hiyo ina maana kwamba thamani ilikuwa chini ya katikati ya
safu, na hivyo tunakwenda kutafuta upande wa kushoto.
Sasa, kushoto ni kwenda kuwa kidogo rahisi kuangalia.
Hivyo, tunaona hapa kwamba sisi ni recursively wito search ambapo kwanza
Hoja ni kwamba, tena, thamani sisi ni kuangalia juu.
Hoja ya pili ni kwenda kuwa safu kwamba tulikuwa kutafuta juu.
Na hiki mwisho sasa ni katikati.
Kumbuka parameter mwisho ni int wetu n, hivyo kwamba ni urefu wa safu yetu.
>> Katika wito kujirudia kutafuta, sisi ni sasa kusema kwamba urefu wa
safu ni katikati.
Hivyo, kama safu yetu ilikuwa ya ukubwa 20 na sisi searched katika index 10, tangu katikati ni
20 kugawanywa na 2, hiyo ina maana sisi ni kupita 10 kama mpya
urefu wa safu yetu.
Kumbuka kwamba wakati una safu urefu wa 10, hiyo ina maana halali
mambo ni katika fahirisi 0 kupitia 9.
Hivyo hii ni nini hasa tunataka bayana safu yetu updated - upande wa kushoto
safu kutoka hiki katikati.
>> Kwa hiyo, kuangalia kwa haki ni vigumu kidogo zaidi.
Sasa kwanza, hebu fikiria urefu ya safu na haki ya
katikati hiki.
Hivyo, kama safu yetu ilikuwa ya ukubwa n, kisha safu mpya itakuwa ya ukubwa n minus
minus katikati 1.
Kwa hiyo, hebu fikiria ya n minus katikati.
>> Tena, kama safu yalikuwa ya kipimo 20 na sisi kugawanya na 2 kupata katikati,
hivyo katikati ni 10, kisha n minus katikati ni kwenda kutupa 10, hivyo 10
mambo ya haki ya katikati.
Lakini pia tuna minus hii 1, tangu sisi hawataki
ni pamoja na katikati yenyewe.
Hivyo n minus katikati minus 1 inatupa jumla ya idadi ya mambo ya haki
ya katikati index katika safu.
>> Sasa hapa, kumbuka kwamba katikati parameter ni maadili safu.
Hivyo hapa, sisi ni kupita updated maadili safu.
Hii maadili pamoja na katikati plus 1 ni kweli kusema recursively simu
search, kupita katika safu mpya, ambapo kwamba safu mpya kuanza katikati
pamoja na moja ya maadili yetu ya awali safu.
>> syntax mbadala kwa ajili ya kwamba, sasa umeingia kuona kuyatumia, ni
maadili Ampersand katikati pamoja na 1.
Hivyo, kunyakua pepe ya katikati pamoja na moja ya kipengele cha maadili.
>> Sasa, ikiwa hawakuridhishwa kubadilisha safu kama kwamba,
inaweza pia kuwa kutekelezwa hii kwa kutumia kujirudia msaidizi kazi, ambapo
kwamba msaidizi kazi inachukua hoja zaidi.
Hivyo badala ya kuchukua tu thamani, safu, na ukubwa wa safu,
msaidizi kazi inaweza kuchukua zaidi hoja, ikiwa ni pamoja na index chini
kuwa wewe huduma ya juu katika safu na index ya juu kwamba huduma
kuhusu safu.
>> Na hivyo kuweka wimbo wa wote chini index na juu index, huna
haja ya milele kurekebisha maadili ya awali safu.
Unaweza tu kuendelea kutumia maadili safu.
Lakini hapa, taarifa hatuna haja msaidizi kazi kwa muda mrefu kama sisi ni
tayari kurekebisha awali maadili safu.
Tuko tayari kupita katika updated maadili.
>> Sasa, hatuwezi search binary juu ya safu kwamba ni zisizochambuliwa.
Hivyo, hebu kupata hii namna.
Sasa, taarifa aina hiyo ni miwili iliyopita vigezo int maadili, ambayo ni
safu kwamba sisi ni kuchagua, na int n, ambayo ni urefu wa safu kwamba
sisi ni kuchagua.
Kwa hiyo, hapa tunataka kutekeleza algorithm kuchagua
kwamba ni o ya n mraba.
Unaweza kuchagua Bubble aina, uteuzi aina, au kuingizwa aina, au
baadhi aina nyingine tuna si kuonekana katika darasa.
Lakini hapa, tunakwenda kutumia uteuzi aina.
>> Kwa hiyo, tunakwenda iterate juu ya safu nzima.
Naam, hapa tunaona kwamba sisi ni iterating kutoka kwa 0 n minus 1.
Kwa nini si njia yote hadi n?
Naam, kama tumekuwa tayari yamepangwa kwanza n minus 1 vipengele, kisha
hiki mwisho sana kile ambacho ni lazima kuwa tayari katika mahali sahihi, hivyo kuchagua juu ya
safu nzima.
>> Sasa, kumbuka jinsi uteuzi aina kazi.
Sisi ni kwenda juu ya safu nzima kuangalia kwa thamani ya chini katika
safu na fimbo kwamba mwanzoni.
Kisha sisi ni kwenda kwa kipindi chote safu tena kuangalia kwa pili
ndogo hiki, na fimbo kwamba katika nafasi ya pili katika
safu, na kadhalika.
Hivyo, kwamba ni nini hii ni kufanya.
>> Hapa, sisi ni kuona kwamba sisi ni kuweka kiwango cha chini sasa
thamani kwa i-th index.
Kadhalika iteration kwanza, tunakwenda kufikiria thamani ya chini kuwa
mwanzo wa safu yetu.
Basi, tunakwenda iterate juu ya salio wa safu, kuangalia kwa
kuona kama kuna mambo yoyote ndogo kuliko moja kwamba sisi ni sasa
kuzingatia kiwango cha chini.
>> Hivyo hapa, maadili j plus moja - hiyo ni kidogo kuliko kile sisi ni sasa
kuzingatia kiwango cha chini.
Kisha tunakwenda update nini tunafikiri ni kiwango cha chini kwa
index j plus 1.
Hivyo, kufanya kuwa katika safu nzima, na baada ya hii kwa kitanzi, kiwango cha chini
lazima hiki kima cha chini kutoka i-th nafasi katika safu.
>> Mara baada ya sisi na kwamba, tunaweza kubadilishana thamani ya chini ndani ya i-th nafasi
katika safu.
Hivyo hii ni kubadilishana ya kiwango.
Sisi kuhifadhi katika thamani ya muda - i-th thamani katika safu -
kuweka katika i-th thamani katika safu thamani kima cha chini ambayo ni huko,
na kisha kuhifadhi nyuma katika ambapo thamani ya sasa kima cha chini cha kutumika kuwa
i-th thamani katika safu, hivyo kwamba hatukuwa kupoteza yake.
>> Kwa hiyo, ambayo inaendelea juu ya iteration ijayo.
Tutaweza kuanza kuangalia kwa pili thamani ya chini na kuingiza kwamba katika
pili ya msimamo.
On iteration tatu, tutaweza kuangalia kwa thamani ya tatu chini na kuingiza
kwamba katika nafasi ya tatu, na hivyo juu ya mpaka tuna safu sorted.
Jina langu ni Rob, na hii mara uteuzi aina.