[MIZIK jwe] 

Doug Lloyd: Tout dwat. Se konsa, rechèch binè se yon algorithm nou ka sèvi ak jwenn yon eleman andedan nan yon etalaj. Kontrèman ak rechèch lineyè, li mande pou yon kondisyon espesyal, ki dwe te rankontre davans, men li la pou pi plis efikas si ke kondisyon se, an reyalite, te rankontre. 

Se konsa, sa ki nan lide nan isit la? li nan separe ak konkeri. Nou vle redwi gwosè a nan zòn nan rechèch pa mwatye chak fwa yo nan lòd yo jwenn yon nimewo sib. Sa a se kote ke kondisyon vin antre nan jwe, menm si. Nou kapab sèlman ogmante pouvwa a nan elimine mwatye nan eleman yo san yo pa menm gade nan yo si se etalaj la Ranje. 

Si li nan yon melanj ranpli moute, nou pa kapab jis anba men jete mwatye nan eleman yo, paske nou pa konnen ki sa nou ap jete. Men, si se etalaj la Ranje, nou ka fè sa, paske nou konnen ke tout bagay sa yo nan rete nan kote nou kounye a yo se dwe pi ba pase nan valè nou ap kounye a nan. Apre sa, tout bagay sa yo nan dwat Bondye ki gen kote nou ye dwe pi gran pase valè a nou ap kounye a kap nan. 

Se konsa, sa ki nan pseudocode a etap pou rechèch binè? Nou repete pwosesis sa a jouk nan etalaj oubyen, jan nou kontinye nan, ranje sub, ki pi piti moso nan etalaj orijinal la, se nan gwosè 0. Kalkile pwen milye a nan etalaj la sub aktyèl la. 

Si valè a ou ap chèche pou se nan ki eleman nan etalaj la, sispann. Ou te jwenn li. Sa bon. Sinon, si sib la se mwens pase sa ki nan nan mitan an, Se konsa, si valè a nou ap chèche pou se pi ba pase sa nou wè, repete pwosesis sa a ankò, men chanje pwen an fen, olye pou pou yo te orijinal la ranpli etalaj plen, yo dwe jis sou bò goch la nan kote nou jis gade. 

Nou te konnen ke mitan an te twò wo, oswa sib la te mwens pase mitan an, Se konsa, li dwe egziste, si li egziste nan tout nan etalaj la, yon kote nan kite nan pwen milye a. Se konsa, nou pral mete etalaj la kote jis sou bò goch la a pwen milye a kòm pwen nan fen nouvo. Kontrèman, si sib la se pi gran pase sa ki nan nan mitan an, nou fè menm bagay la egzak pwosesis, men olye nou chanje pwen an kòmanse yo dwe jis a dwat a pwen milye a nou jis kalkile. Lè sa a,, nou kòmanse pwosesis la ankò. 

Se pou nou visualized sa a, OK? Se konsa, gen nan yon anpil pral ak sou isit la, men isit la nan yon etalaj de 15 eleman yo. Epi nou ap ale nan dwe kenbe tras nan yon anpil plis bagay tan sa a. Se konsa, nan rechèch lineyè, nou te jis pran swen sou yon sib. Men, tan sa a nou vle pran swen sou kote yo nou kòmanse gade, kote yo nou kanpe kap, ak sa ki nan pwen milye a nan etalaj aktyèl la. Se konsa, isit la nou ale ak rechèch binè. Nou bèl anpil bon yo ale, dwa? Mwen jis ale nan mete desann anba a isit la yon seri endis. Sa a se fondamantalman jis sa eleman nan etalaj la nou ap pale de. Avèk rechèch lineyè, nou pran swen, toutotan nou bezwen konnen ki jan anpil eleman nou ap iteration sou yo, men nou pa aktyèlman pran swen sa eleman nou ap kounye a kap nan. Nan rechèch binè, nou fè. Se konsa, sa yo se jis gen kòm yon ti kras gid. 

Se konsa, nou ka kòmanse, dwa? Oke, pa byen. Sonje sa m 'te di sou rechèch binè? Nou pa ka fè l 'sou yon etalaj triye oswa lòt moun, nou pa garanti ke a sèten eleman oswa valè yo pa ke yo te aksidantèlman abandone lè nou jis deside inyore mwatye nan etalaj la. 

Se konsa, etap yon sèl ak rechèch binè se ou dwe gen yon etalaj Ranje. Epi ou ka itilize nenpòt nan klasman an algoritm nou te te pale osijè de fè ou jwenn ak sa yo ki pozisyon. Se konsa, kounye a, nou ap nan yon pozisyon kote nou ka fè binè rechèch. 

Se konsa nou repete pwosesis la etap pa etap epi kenbe tras nan sa k ap pase kòm nou ale. Se konsa, premye nou bezwen nan fè se kalkile pwen milye a nan etalaj aktyèl la. Bon, nou pral di nou ap, premye a tout, kap chèche valè a 19. Nou ap eseye jwenn kantite a 19. Eleman an premye nan sa a se etalaj ki chita nan endèks zewo, ak eleman ki sot pase a nan sa a se etalaj ki chita nan endèks 14. Se konsa, nou pral rele moun kòmansman ak nan fen. 

Se konsa, nou kalkile pwen milye a pa ajoute 0 plis 14 divize pa 2; trè dwat pwen milye. Apre sa, nou ka di ke pwen milye a se kounye a 7. Se konsa, se 15 sa nou ap chèche pou? Non, li pa. Nou ap chèche pou 19. Men, nou konnen 19 gen plis pouvwa pase sa nou jwenn nan mitan yo. 

Se konsa, sa nou ka fè se chanje pwen an kòmanse yo dwe jis a dwat a nan pwen milye, ak repete pwosesis la ankò. Lè nou fè sa, nou kounye a di nan nouvo pwen kòmansman se etalaj kote 8. Ki sa nou te fè se efektivman inyore tout bagay sa yo bò gòch la nan 15. Nou te elimine mwatye nan pwoblèm nan, epi kounye a, olye pou yo gen fè rechèch plis pase 15 eleman nan etalaj nou an, nou sèlman gen nan rechèch plis pase 7. Se konsa, 8 se pwen an kòmanse nouvo. 14 se toujou pwen an fen. 

Epi, koulye a, nou ale sou sa a ankò. Nou kalkile pwen milye a nouvo. 8 plis 14 se 22, divize pa 2 se 11. Eske se sou sa nou ap chèche pou? Non, li pa. Nou ap chèche pou se yon valè sa a, se mwens pase sa nou jis te jwenn. Se konsa, nou ap ale nan repete pwosesis la ankò. Nou pwal chanje pwen an fen nan ka jis nan kite nan pwen milye a. Se konsa, pwen an fen nouvo vin 10. Koulye a, sa a, se yon pati nan sèlman nan etalaj la nou gen sòt nan. Se konsa, nou gen kounye a elimine 12 nan 15 eleman yo. Nou konnen ke si 19 egziste nan etalaj la, li dwe egziste yon kote ant eleman Nimewo 8 ak eleman Nimewo 10. 

Se konsa, nou kalkile pwen milye a nouvo ankò. 8 plis 10 se 18, divize pa 2 se 9. Ak nan ka sa a, gade, an sib se nan mitan yo. Nou jwenn ekzakteman ki sa nou ap chèche pou. Nou ka sispann. Nou konplete avèk siksè yon rechèch binè. Tout dwa. Se konsa, nou konnen sa a algorithm travay si sib la se yon kote andedan nan etalaj la. Èske travay sa a algorithm si sib la se pa nan etalaj la? Oke, kite la kòmanse li ankò, li tan sa a, se pou yo gade pou eleman nan 16, ki vizyèlman nou ka wè pa egziste nenpòt kote nan etalaj la. 

Pwen an kòmanse se ankò 0. Pwen an fen se ankò 14. Moun sa yo se endis yo nan premye a ak eleman sot pase yo nan etalaj la konplè. Epitou, n ap ale atravè tout pwosesis la nou jis mache ale nan tout ankò, ap eseye jwenn 16, menm si vizyèlman, nou ka deja di ke li pa k ap pase yo dwe la. Nou jis vle asire w ke sa a algorithm pral, an reyalite, toujou travay nan kèk fason epi li pa jis kite nou kole nan yon riban enfini. 

Se konsa, sa ki nan etap la an premye? Kalkile pwen milye a nan etalaj aktyèl la. Ki sa ki nan pwen milye a nan etalaj la ye kounye a? Oke, li nan 7, dwa? 14 plis 0 divize pa 2 se 7. Se 15 sa nou ap chèche pou? No Li trè fèmen, men nou ap chèche pou yon valè yon ti kras pi gwo pase sa. 

Se konsa, nou konnen ke li k ap pase yo gen okenn kote nan kite nan 15. Sib la gen plis pouvwa pase sa ki nan pwen milye a. Se konsa, nou mete pwen an kòmanse nouvo nan ka jis a dwat a mitan yo. Pwen milye a se kounye a 7, se konsa kite a di pwen an kòmanse nouvo se 8. Ak sa ki nou te efektivman fè ankò se inyore tout mwatye nan gòch nan etalaj la. 

Koulye a, nou repete nan travay sou yon lòt fwa ankò. Kalkile pwen milye a nouvo. 8 plis 14 se 22, divize pa 2 se 11. Se 23 sa nou ap chèche pou? Malerezman, pa gen okenn. Nou ap chèche pou se yon valè ki se mwens pase 23. Se konsa, nan ka sa a, nou ap ale chanje pwen an fen yo dwe jis nan kite nan pwen milye aktyèl la. Pwen milye ki la kounye a se 11, ak se konsa nou pral mete pwen an fen nouvo pou tan nan pwochen te nou ale atravè tout pwosesis sa a nan 10. 

Yon fwa ankò, nou ale atravè tout pwosesis la ankò. Kalkile pwen milye a. 8 plis 10 divize pa 2 se 9. Se 19 sa nou ap chèche pou? Malerezman, pa gen okenn. Nou ap toujou kap chèche yon PO mwens pase sa. Se konsa, nou pral chanje pwen an fen tan sa a yo dwe jis nan kite nan pwen milye a. Pwen milye a se kounye a 9, se konsa pwen an fen yo pral 8. Epi, koulye a, nou ap jis kap Yon etalaj eleman sèl. 

Ki sa ki nan pwen milye a nan etalaj sa a? Oke, li kòmanse nan 8, li fini nan 8, pwen milye a se 8. Eske se sa ke sa nou ap chèche pou? Èske nou chèche pou 17? Non, nou ap chèche pou 16. Se konsa, si li egziste nan etalaj la, li dwe egziste yon kote nan kite nan kote nou kounye a ye. Se konsa, sa nou pral fè? Oke, nou pral mete pwen an fen yo dwe jis nan kite nan pwen milye aktyèl la. Se konsa, nou pral chanje pwen an fen nan 7. Ou wè sa ki jis ki te pase isit la, menm si? Gade moute isit la kounye a. 

Start se kounye a pi gran pase fen. Efektivman, de pwent yo nan etalaj nou yo te janbe lòt, ak pwen an kòmanse se kounye a apre pwen an fen. Oke, ki pa fè sa fè okenn sans, dwa? Se konsa, kounye, ki sa nou ka di se nou gen yon etalaj sub nan gwosè 0. Ak yon lòt fwa nou ap vinn pwen sa a, nou kapab kounye a garanti ke eleman 16 pa egziste nan etalaj la, paske pwen an kòmanse epi yo gen fen pwen janbe lòt. Se konsa, li nan pa la. Koulye a, remake ke sa a se yon ti kras diferan pase pwen an kòmanse ak nan fen pwen ke yo te menm bagay la. Si nou te viv kap pou 17, li ta gen te nan etalaj la, ak pwen an kòmanse ak nan fen pwen nan ki iterasyon dènye anvan pwen sa yo janbe lòt, nou ta yo te jwenn 17 a. Li nan sèlman lè yo travèse ke nou kapab garanti ke eleman nan pa fè sa egziste nan etalaj la. 

Se konsa, kite a pran yon anpil mwens etap pase rechèch lineyè. Nan senaryo a ka pi mal la, nou te gen a fann moute yon lis nan eleman n repete nan mwatye jwenn sib la, swa paske eleman nan sib yo pral yon kote nan dènye a divizyon, oswa li pa egziste nan tout. Se konsa, nan ka ki pi mal, nou gen yo fann moute array-- yo ou konnen? Log nan fwa n; nou gen nan koupe pwoblèm nan nan mwatye yon sèten kantite fwa. Sa kantite fwa se boutèy demi lit n. 

Ki sa ki nan senaryo a ka pi bon? Bon, nou nan tan premye kalkile pwen milye a, nou jwenn sa nou ap chèche pou. Nan tout anvan an egzanp sou rechèch binè nou te jis ale sou yo, si nou te gen te kap chèche eleman nan 15, nou ta yo te jwenn ke imedyatman. Sa ki te nan konmansman an anpil. Sa ki te pwen milye a nan tantativ an premye nan yon dezinyon nan yon divizyon nan binè rechèch. 

Se konsa, nan pi move a ka, rechèch binè kouri nan boutèy demi lit n, ki se pi bon anpil pase rechèch lineyè, nan ka ki pi mal la. Nan ka ki pi bon, binè rechèch kouri nan Omega nan 1. Se konsa, rechèch binè se yon anpil pi bon pase rechèch lineyè, men ou gen fè fas ak pwosesis la nan Fouye etalaj ou premye anvan ou kapab ogmante pouvwa a nan rechèch binè. 

Mwen se Doug Lloyd. Sa a se CS 50.