1 00:00:00,000 --> 00:00:03,346 >> [MIZIK jwe] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> Doug Lloyd: Tout dwat. 4 00:00:06,220 --> 00:00:08,140 Se konsa, rechèch binè se yon algorithm nou ka sèvi ak 5 00:00:08,140 --> 00:00:10,530 jwenn yon eleman andedan nan yon etalaj. 6 00:00:10,530 --> 00:00:14,710 Kontrèman ak rechèch lineyè, li mande pou yon kondisyon espesyal, ki dwe te rankontre davans, 7 00:00:14,710 --> 00:00:19,020 men li la pou pi plis efikas si ke kondisyon se, an reyalite, te rankontre. 8 00:00:19,020 --> 00:00:20,470 >> Se konsa, sa ki nan lide nan isit la? 9 00:00:20,470 --> 00:00:21,780 li nan separe ak konkeri. 10 00:00:21,780 --> 00:00:25,100 Nou vle redwi gwosè a nan zòn nan rechèch pa mwatye chak fwa 11 00:00:25,100 --> 00:00:27,240 yo nan lòd yo jwenn yon nimewo sib. 12 00:00:27,240 --> 00:00:29,520 Sa a se kote ke kondisyon vin antre nan jwe, menm si. 13 00:00:29,520 --> 00:00:32,740 Nou kapab sèlman ogmante pouvwa a nan elimine mwatye nan eleman yo 14 00:00:32,740 --> 00:00:36,070 san yo pa menm gade nan yo si se etalaj la Ranje. 15 00:00:36,070 --> 00:00:39,200 >> Si li nan yon melanj ranpli moute, nou pa kapab jis anba men 16 00:00:39,200 --> 00:00:42,870 jete mwatye nan eleman yo, paske nou pa konnen ki sa nou ap jete. 17 00:00:42,870 --> 00:00:45,624 Men, si se etalaj la Ranje, nou ka fè sa, paske nou 18 00:00:45,624 --> 00:00:48,040 konnen ke tout bagay sa yo nan rete nan kote nou kounye a yo se 19 00:00:48,040 --> 00:00:50,500 dwe pi ba pase nan valè nou ap kounye a nan. 20 00:00:50,500 --> 00:00:52,300 Apre sa, tout bagay sa yo nan dwat Bondye ki gen kote nou ye 21 00:00:52,300 --> 00:00:55,040 dwe pi gran pase valè a nou ap kounye a kap nan. 22 00:00:55,040 --> 00:00:58,710 >> Se konsa, sa ki nan pseudocode a etap pou rechèch binè? 23 00:00:58,710 --> 00:01:02,310 Nou repete pwosesis sa a jouk nan etalaj oubyen, jan nou kontinye nan, 24 00:01:02,310 --> 00:01:07,740 ranje sub, ki pi piti moso nan etalaj orijinal la, se nan gwosè 0. 25 00:01:07,740 --> 00:01:10,960 Kalkile pwen milye a nan etalaj la sub aktyèl la. 26 00:01:10,960 --> 00:01:14,460 >> Si valè a ou ap chèche pou se nan ki eleman nan etalaj la, sispann. 27 00:01:14,460 --> 00:01:15,030 Ou te jwenn li. 28 00:01:15,030 --> 00:01:16,550 Sa bon. 29 00:01:16,550 --> 00:01:19,610 Sinon, si sib la se mwens pase sa ki nan nan mitan an, 30 00:01:19,610 --> 00:01:23,430 Se konsa, si valè a nou ap chèche pou se pi ba pase sa nou wè, 31 00:01:23,430 --> 00:01:26,780 repete pwosesis sa a ankò, men chanje pwen an fen, olye pou 32 00:01:26,780 --> 00:01:29,300 pou yo te orijinal la ranpli etalaj plen, 33 00:01:29,300 --> 00:01:34,110 yo dwe jis sou bò goch la nan kote nou jis gade. 34 00:01:34,110 --> 00:01:38,940 >> Nou te konnen ke mitan an te twò wo, oswa sib la te mwens pase mitan an, 35 00:01:38,940 --> 00:01:42,210 Se konsa, li dwe egziste, si li egziste nan tout nan etalaj la, 36 00:01:42,210 --> 00:01:44,660 yon kote nan kite nan pwen milye a. 37 00:01:44,660 --> 00:01:48,120 Se konsa, nou pral mete etalaj la kote jis sou bò goch la 38 00:01:48,120 --> 00:01:51,145 a pwen milye a kòm pwen nan fen nouvo. 39 00:01:51,145 --> 00:01:53,770 Kontrèman, si sib la se pi gran pase sa ki nan nan mitan an, 40 00:01:53,770 --> 00:01:55,750 nou fè menm bagay la egzak pwosesis, men olye nou 41 00:01:55,750 --> 00:01:59,520 chanje pwen an kòmanse yo dwe jis a dwat a pwen milye a 42 00:01:59,520 --> 00:02:00,680 nou jis kalkile. 43 00:02:00,680 --> 00:02:03,220 Lè sa a,, nou kòmanse pwosesis la ankò. 44 00:02:03,220 --> 00:02:05,220 >> Se pou nou visualized sa a, OK? 45 00:02:05,220 --> 00:02:08,620 Se konsa, gen nan yon anpil pral ak sou isit la, men isit la nan yon etalaj de 15 eleman yo. 46 00:02:08,620 --> 00:02:11,400 Epi nou ap ale nan dwe kenbe tras nan yon anpil plis bagay tan sa a. 47 00:02:11,400 --> 00:02:13,870 Se konsa, nan rechèch lineyè, nou te jis pran swen sou yon sib. 48 00:02:13,870 --> 00:02:15,869 Men, tan sa a nou vle pran swen sou kote yo nou 49 00:02:15,869 --> 00:02:18,480 kòmanse gade, kote yo nou kanpe kap, 50 00:02:18,480 --> 00:02:21,876 ak sa ki nan pwen milye a nan etalaj aktyèl la. 51 00:02:21,876 --> 00:02:23,250 Se konsa, isit la nou ale ak rechèch binè. 52 00:02:23,250 --> 00:02:25,290 Nou bèl anpil bon yo ale, dwa? 53 00:02:25,290 --> 00:02:28,650 Mwen jis ale nan mete desann anba a isit la yon seri endis. 54 00:02:28,650 --> 00:02:32,430 Sa a se fondamantalman jis sa eleman nan etalaj la nou ap pale de. 55 00:02:32,430 --> 00:02:34,500 Avèk rechèch lineyè, nou pran swen, toutotan nou 56 00:02:34,500 --> 00:02:36,800 bezwen konnen ki jan anpil eleman nou ap iteration sou yo, 57 00:02:36,800 --> 00:02:40,010 men nou pa aktyèlman pran swen sa eleman nou ap kounye a kap nan. 58 00:02:40,010 --> 00:02:41,014 Nan rechèch binè, nou fè. 59 00:02:41,014 --> 00:02:42,930 Se konsa, sa yo se jis gen kòm yon ti kras gid. 60 00:02:42,930 --> 00:02:44,910 >> Se konsa, nou ka kòmanse, dwa? 61 00:02:44,910 --> 00:02:46,240 Oke, pa byen. 62 00:02:46,240 --> 00:02:48,160 Sonje sa m 'te di sou rechèch binè? 63 00:02:48,160 --> 00:02:50,955 Nou pa ka fè l 'sou yon etalaj triye oswa lòt moun, 64 00:02:50,955 --> 00:02:55,820 nou pa garanti ke a sèten eleman oswa valè yo pa 65 00:02:55,820 --> 00:02:57,650 ke yo te aksidantèlman abandone lè nou jis 66 00:02:57,650 --> 00:02:59,920 deside inyore mwatye nan etalaj la. 67 00:02:59,920 --> 00:03:02,574 >> Se konsa, etap yon sèl ak rechèch binè se ou dwe gen yon etalaj Ranje. 68 00:03:02,574 --> 00:03:05,240 Epi ou ka itilize nenpòt nan klasman an algoritm nou te te pale osijè de 69 00:03:05,240 --> 00:03:06,700 fè ou jwenn ak sa yo ki pozisyon. 70 00:03:06,700 --> 00:03:10,370 Se konsa, kounye a, nou ap nan yon pozisyon kote nou ka fè binè rechèch. 71 00:03:10,370 --> 00:03:12,560 >> Se konsa nou repete pwosesis la etap pa etap epi kenbe 72 00:03:12,560 --> 00:03:14,830 tras nan sa k ap pase kòm nou ale. 73 00:03:14,830 --> 00:03:17,980 Se konsa, premye nou bezwen nan fè se kalkile pwen milye a nan etalaj aktyèl la. 74 00:03:17,980 --> 00:03:20,620 Bon, nou pral di nou ap, premye a tout, kap chèche valè a 19. 75 00:03:20,620 --> 00:03:22,290 Nou ap eseye jwenn kantite a 19. 76 00:03:22,290 --> 00:03:25,380 Eleman an premye nan sa a se etalaj ki chita nan endèks zewo, 77 00:03:25,380 --> 00:03:28,880 ak eleman ki sot pase a nan sa a se etalaj ki chita nan endèks 14. 78 00:03:28,880 --> 00:03:31,430 Se konsa, nou pral rele moun kòmansman ak nan fen. 79 00:03:31,430 --> 00:03:35,387 >> Se konsa, nou kalkile pwen milye a pa ajoute 0 plis 14 divize pa 2; 80 00:03:35,387 --> 00:03:36,720 trè dwat pwen milye. 81 00:03:36,720 --> 00:03:40,190 Apre sa, nou ka di ke pwen milye a se kounye a 7. 82 00:03:40,190 --> 00:03:43,370 Se konsa, se 15 sa nou ap chèche pou? 83 00:03:43,370 --> 00:03:43,940 Non, li pa. 84 00:03:43,940 --> 00:03:45,270 Nou ap chèche pou 19. 85 00:03:45,270 --> 00:03:49,400 Men, nou konnen 19 gen plis pouvwa pase sa nou jwenn nan mitan yo. 86 00:03:49,400 --> 00:03:52,470 >> Se konsa, sa nou ka fè se chanje pwen an kòmanse 87 00:03:52,470 --> 00:03:57,280 yo dwe jis a dwat a nan pwen milye, ak repete pwosesis la ankò. 88 00:03:57,280 --> 00:04:01,690 Lè nou fè sa, nou kounye a di nan nouvo pwen kòmansman se etalaj kote 8. 89 00:04:01,690 --> 00:04:07,220 Ki sa nou te fè se efektivman inyore tout bagay sa yo bò gòch la nan 15. 90 00:04:07,220 --> 00:04:09,570 Nou te elimine mwatye nan pwoblèm nan, epi kounye a, 91 00:04:09,570 --> 00:04:13,510 olye pou yo gen fè rechèch plis pase 15 eleman nan etalaj nou an, 92 00:04:13,510 --> 00:04:15,610 nou sèlman gen nan rechèch plis pase 7. 93 00:04:15,610 --> 00:04:17,706 Se konsa, 8 se pwen an kòmanse nouvo. 94 00:04:17,706 --> 00:04:19,600 14 se toujou pwen an fen. 95 00:04:19,600 --> 00:04:21,430 >> Epi, koulye a, nou ale sou sa a ankò. 96 00:04:21,430 --> 00:04:22,810 Nou kalkile pwen milye a nouvo. 97 00:04:22,810 --> 00:04:27,130 8 plis 14 se 22, divize pa 2 se 11. 98 00:04:27,130 --> 00:04:28,660 Eske se sou sa nou ap chèche pou? 99 00:04:28,660 --> 00:04:30,110 Non, li pa. 100 00:04:30,110 --> 00:04:32,930 Nou ap chèche pou se yon valè sa a, se mwens pase sa nou jis te jwenn. 101 00:04:32,930 --> 00:04:34,721 Se konsa, nou ap ale nan repete pwosesis la ankò. 102 00:04:34,721 --> 00:04:38,280 Nou pwal chanje pwen an fen nan ka jis nan kite nan pwen milye a. 103 00:04:38,280 --> 00:04:41,800 Se konsa, pwen an fen nouvo vin 10. 104 00:04:41,800 --> 00:04:44,780 Koulye a, sa a, se yon pati nan sèlman nan etalaj la nou gen sòt nan. 105 00:04:44,780 --> 00:04:48,460 Se konsa, nou gen kounye a elimine 12 nan 15 eleman yo. 106 00:04:48,460 --> 00:04:51,550 Nou konnen ke si 19 egziste nan etalaj la, li 107 00:04:51,550 --> 00:04:57,210 dwe egziste yon kote ant eleman Nimewo 8 ak eleman Nimewo 10. 108 00:04:57,210 --> 00:04:59,400 >> Se konsa, nou kalkile pwen milye a nouvo ankò. 109 00:04:59,400 --> 00:05:02,900 8 plis 10 se 18, divize pa 2 se 9. 110 00:05:02,900 --> 00:05:05,074 Ak nan ka sa a, gade, an sib se nan mitan yo. 111 00:05:05,074 --> 00:05:06,740 Nou jwenn ekzakteman ki sa nou ap chèche pou. 112 00:05:06,740 --> 00:05:07,780 Nou ka sispann. 113 00:05:07,780 --> 00:05:10,561 Nou konplete avèk siksè yon rechèch binè. 114 00:05:10,561 --> 00:05:11,060 Tout dwa. 115 00:05:11,060 --> 00:05:13,930 Se konsa, nou konnen sa a algorithm travay si sib la se 116 00:05:13,930 --> 00:05:16,070 yon kote andedan nan etalaj la. 117 00:05:16,070 --> 00:05:19,060 Èske travay sa a algorithm si sib la se pa nan etalaj la? 118 00:05:19,060 --> 00:05:20,810 Oke, kite la kòmanse li ankò, li tan sa a, 119 00:05:20,810 --> 00:05:23,380 se pou yo gade pou eleman nan 16, ki vizyèlman nou ka wè 120 00:05:23,380 --> 00:05:25,620 pa egziste nenpòt kote nan etalaj la. 121 00:05:25,620 --> 00:05:27,110 >> Pwen an kòmanse se ankò 0. 122 00:05:27,110 --> 00:05:28,590 Pwen an fen se ankò 14. 123 00:05:28,590 --> 00:05:32,490 Moun sa yo se endis yo nan premye a ak eleman sot pase yo nan etalaj la konplè. 124 00:05:32,490 --> 00:05:36,057 Epitou, n ap ale atravè tout pwosesis la nou jis mache ale nan tout ankò, ap eseye jwenn 16, 125 00:05:36,057 --> 00:05:39,140 menm si vizyèlman, nou ka deja di ke li pa k ap pase yo dwe la. 126 00:05:39,140 --> 00:05:43,450 Nou jis vle asire w ke sa a algorithm pral, an reyalite, toujou travay nan kèk fason 127 00:05:43,450 --> 00:05:46,310 epi li pa jis kite nou kole nan yon riban enfini. 128 00:05:46,310 --> 00:05:48,190 >> Se konsa, sa ki nan etap la an premye? 129 00:05:48,190 --> 00:05:50,230 Kalkile pwen milye a nan etalaj aktyèl la. 130 00:05:50,230 --> 00:05:52,790 Ki sa ki nan pwen milye a nan etalaj la ye kounye a? 131 00:05:52,790 --> 00:05:54,410 Oke, li nan 7, dwa? 132 00:05:54,410 --> 00:05:57,560 14 plis 0 divize pa 2 se 7. 133 00:05:57,560 --> 00:05:59,280 Se 15 sa nou ap chèche pou? 134 00:05:59,280 --> 00:05:59,780 No 135 00:05:59,780 --> 00:06:02,930 Li trè fèmen, men nou ap chèche pou yon valè yon ti kras pi gwo pase sa. 136 00:06:02,930 --> 00:06:06,310 >> Se konsa, nou konnen ke li k ap pase yo gen okenn kote nan kite nan 15. 137 00:06:06,310 --> 00:06:08,540 Sib la gen plis pouvwa pase sa ki nan pwen milye a. 138 00:06:08,540 --> 00:06:12,450 Se konsa, nou mete pwen an kòmanse nouvo nan ka jis a dwat a mitan yo. 139 00:06:12,450 --> 00:06:16,130 Pwen milye a se kounye a 7, se konsa kite a di pwen an kòmanse nouvo se 8. 140 00:06:16,130 --> 00:06:18,130 Ak sa ki nou te efektivman fè ankò se inyore 141 00:06:18,130 --> 00:06:21,150 tout mwatye nan gòch nan etalaj la. 142 00:06:21,150 --> 00:06:23,750 >> Koulye a, nou repete nan travay sou yon lòt fwa ankò. 143 00:06:23,750 --> 00:06:24,910 Kalkile pwen milye a nouvo. 144 00:06:24,910 --> 00:06:29,350 8 plis 14 se 22, divize pa 2 se 11. 145 00:06:29,350 --> 00:06:31,060 Se 23 sa nou ap chèche pou? 146 00:06:31,060 --> 00:06:31,870 Malerezman, pa gen okenn. 147 00:06:31,870 --> 00:06:34,930 Nou ap chèche pou se yon valè ki se mwens pase 23. 148 00:06:34,930 --> 00:06:37,850 Se konsa, nan ka sa a, nou ap ale chanje pwen an fen yo dwe jis 149 00:06:37,850 --> 00:06:40,035 nan kite nan pwen milye aktyèl la. 150 00:06:40,035 --> 00:06:43,440 Pwen milye ki la kounye a se 11, ak se konsa nou pral mete pwen an fen nouvo 151 00:06:43,440 --> 00:06:46,980 pou tan nan pwochen te nou ale atravè tout pwosesis sa a nan 10. 152 00:06:46,980 --> 00:06:48,660 >> Yon fwa ankò, nou ale atravè tout pwosesis la ankò. 153 00:06:48,660 --> 00:06:49,640 Kalkile pwen milye a. 154 00:06:49,640 --> 00:06:53,100 8 plis 10 divize pa 2 se 9. 155 00:06:53,100 --> 00:06:54,750 Se 19 sa nou ap chèche pou? 156 00:06:54,750 --> 00:06:55,500 Malerezman, pa gen okenn. 157 00:06:55,500 --> 00:06:58,050 Nou ap toujou kap chèche yon PO mwens pase sa. 158 00:06:58,050 --> 00:07:02,060 Se konsa, nou pral chanje pwen an fen tan sa a yo dwe jis nan kite nan pwen milye a. 159 00:07:02,060 --> 00:07:05,532 Pwen milye a se kounye a 9, se konsa pwen an fen yo pral 8. 160 00:07:05,532 --> 00:07:07,920 Epi, koulye a, nou ap jis kap Yon etalaj eleman sèl. 161 00:07:07,920 --> 00:07:10,250 >> Ki sa ki nan pwen milye a nan etalaj sa a? 162 00:07:10,250 --> 00:07:13,459 Oke, li kòmanse nan 8, li fini nan 8, pwen milye a se 8. 163 00:07:13,459 --> 00:07:14,750 Eske se sa ke sa nou ap chèche pou? 164 00:07:14,750 --> 00:07:16,339 Èske nou chèche pou 17? 165 00:07:16,339 --> 00:07:17,380 Non, nou ap chèche pou 16. 166 00:07:17,380 --> 00:07:20,160 Se konsa, si li egziste nan etalaj la, li dwe egziste yon kote 167 00:07:20,160 --> 00:07:21,935 nan kite nan kote nou kounye a ye. 168 00:07:21,935 --> 00:07:23,060 Se konsa, sa nou pral fè? 169 00:07:23,060 --> 00:07:26,610 Oke, nou pral mete pwen an fen yo dwe jis nan kite nan pwen milye aktyèl la. 170 00:07:26,610 --> 00:07:29,055 Se konsa, nou pral chanje pwen an fen nan 7. 171 00:07:29,055 --> 00:07:32,120 Ou wè sa ki jis ki te pase isit la, menm si? 172 00:07:32,120 --> 00:07:33,370 Gade moute isit la kounye a. 173 00:07:33,370 --> 00:07:35,970 >> Start se kounye a pi gran pase fen. 174 00:07:35,970 --> 00:07:39,620 Efektivman, de pwent yo nan etalaj nou yo te janbe lòt, 175 00:07:39,620 --> 00:07:42,252 ak pwen an kòmanse se kounye a apre pwen an fen. 176 00:07:42,252 --> 00:07:43,960 Oke, ki pa fè sa fè okenn sans, dwa? 177 00:07:43,960 --> 00:07:47,960 Se konsa, kounye, ki sa nou ka di se nou gen yon etalaj sub nan gwosè 0. 178 00:07:47,960 --> 00:07:50,110 Ak yon lòt fwa nou ap vinn pwen sa a, nou kapab kounye a 179 00:07:50,110 --> 00:07:53,940 garanti ke eleman 16 pa egziste nan etalaj la, 180 00:07:53,940 --> 00:07:56,280 paske pwen an kòmanse epi yo gen fen pwen janbe lòt. 181 00:07:56,280 --> 00:07:58,340 Se konsa, li nan pa la. 182 00:07:58,340 --> 00:08:01,340 Koulye a, remake ke sa a se yon ti kras diferan pase pwen an kòmanse ak nan fen 183 00:08:01,340 --> 00:08:02,900 pwen ke yo te menm bagay la. 184 00:08:02,900 --> 00:08:05,030 Si nou te viv kap pou 17, li ta gen 185 00:08:05,030 --> 00:08:08,870 te nan etalaj la, ak pwen an kòmanse ak nan fen pwen nan ki iterasyon dènye 186 00:08:08,870 --> 00:08:11,820 anvan pwen sa yo janbe lòt, nou ta yo te jwenn 17 a. 187 00:08:11,820 --> 00:08:15,510 Li nan sèlman lè yo travèse ke nou kapab garanti ke eleman nan pa fè sa 188 00:08:15,510 --> 00:08:17,180 egziste nan etalaj la. 189 00:08:17,180 --> 00:08:20,260 >> Se konsa, kite a pran yon anpil mwens etap pase rechèch lineyè. 190 00:08:20,260 --> 00:08:23,250 Nan senaryo a ka pi mal la, nou te gen a fann moute yon lis nan eleman n 191 00:08:23,250 --> 00:08:27,770 repete nan mwatye jwenn sib la, swa paske eleman nan sib 192 00:08:27,770 --> 00:08:33,110 yo pral yon kote nan dènye a divizyon, oswa li pa egziste nan tout. 193 00:08:33,110 --> 00:08:37,830 Se konsa, nan ka ki pi mal, nou gen yo fann moute array-- yo ou konnen? 194 00:08:37,830 --> 00:08:40,510 Log nan fwa n; nou gen nan koupe pwoblèm nan 195 00:08:40,510 --> 00:08:42,610 nan mwatye yon sèten kantite fwa. 196 00:08:42,610 --> 00:08:45,160 Sa kantite fwa se boutèy demi lit n. 197 00:08:45,160 --> 00:08:46,510 >> Ki sa ki nan senaryo a ka pi bon? 198 00:08:46,510 --> 00:08:48,899 Bon, nou nan tan premye kalkile pwen milye a, 199 00:08:48,899 --> 00:08:50,190 nou jwenn sa nou ap chèche pou. 200 00:08:50,190 --> 00:08:52,150 Nan tout anvan an egzanp sou rechèch binè 201 00:08:52,150 --> 00:08:55,489 nou te jis ale sou yo, si nou te gen te kap chèche eleman nan 15, 202 00:08:55,489 --> 00:08:57,030 nou ta yo te jwenn ke imedyatman. 203 00:08:57,030 --> 00:08:58,321 Sa ki te nan konmansman an anpil. 204 00:08:58,321 --> 00:09:01,200 Sa ki te pwen milye a nan tantativ an premye nan yon dezinyon 205 00:09:01,200 --> 00:09:03,950 nan yon divizyon nan binè rechèch. 206 00:09:03,950 --> 00:09:06,350 >> Se konsa, nan pi move a ka, rechèch binè kouri 207 00:09:06,350 --> 00:09:11,580 nan boutèy demi lit n, ki se pi bon anpil pase rechèch lineyè, nan ka ki pi mal la. 208 00:09:11,580 --> 00:09:16,210 Nan ka ki pi bon, binè rechèch kouri nan Omega nan 1. 209 00:09:16,210 --> 00:09:18,990 Se konsa, rechèch binè se yon anpil pi bon pase rechèch lineyè, 210 00:09:18,990 --> 00:09:23,270 men ou gen fè fas ak pwosesis la nan Fouye etalaj ou premye anvan ou kapab 211 00:09:23,270 --> 00:09:26,140 ogmante pouvwa a nan rechèch binè. 212 00:09:26,140 --> 00:09:27,130 >> Mwen se Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 Sa a se CS 50. 214 00:09:29,470 --> 00:09:31,070