1 00:00:00,000 --> 00:00:03,346 >> [Musika jotzen] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG LLOYD: Ondo da. 4 00:00:06,220 --> 00:00:08,140 Beraz, bilaketa bitarra da algoritmoa erabili ahal izango dugu 5 00:00:08,140 --> 00:00:10,530 array baten barruan elementu bat aurkitzeko. 6 00:00:10,530 --> 00:00:14,710 Bilaketa lineala ez bezala, hura eskatzen batean baldintza bereziak izango dira, aldez aurretik ezagutu, 7 00:00:14,710 --> 00:00:19,020 baina hain da askoz eraginkorragoa bada Baldintza hori da, hain zuzen ere, ezagutu. 8 00:00:19,020 --> 00:00:20,470 >> Beraz, zer da ideia hemen? 9 00:00:20,470 --> 00:00:21,780 Banatu eta agindu da. 10 00:00:21,780 --> 00:00:25,100 Tamaina murriztu nahi dugu Bilaketa-denbora erdia bakoitzak zona 11 00:00:25,100 --> 00:00:27,240 Helburu zenbaki bat aurkitzeko. 12 00:00:27,240 --> 00:00:29,520 Hau non baldintza dela sartzen da jokoan, baina. 13 00:00:29,520 --> 00:00:32,740 Dugu bakarrik leverage boterea ezabatuz elementuak erdia 14 00:00:32,740 --> 00:00:36,070 are begiratu gabe Array bada horiek ordenatuko da. 15 00:00:36,070 --> 00:00:39,200 >> Nahasketa up bat da, bada Ezin dugu besterik escutic 16 00:00:39,200 --> 00:00:42,870 elementuak erdia baztertzen dituelako ez dakigu zer baztertzen ari gara. 17 00:00:42,870 --> 00:00:45,624 Baina array ordenatuko da, bada, Hori egin ahal izango dugu, garelako 18 00:00:45,624 --> 00:00:48,040 dena dela jakin non gaur egun gara geldituak 19 00:00:48,040 --> 00:00:50,500 baino txikiagoa izan behar du balio gaur egun ari gara. 20 00:00:50,500 --> 00:00:52,300 Eta guztia egin non gauden eskubidea 21 00:00:52,300 --> 00:00:55,040 balioa baina handiagoa izan behar du Une gara begira. 22 00:00:55,040 --> 00:00:58,710 >> Beraz, zein da pseudocode bilaketa bitarra urratsak? 23 00:00:58,710 --> 00:01:02,310 Prozesu hau errepikatu dugu arte array edo, bidez jarraitu dugu, 24 00:01:02,310 --> 00:01:07,740 sub matrizeak, pieza txikiagoak jatorrizko array, tamaina 0 da. 25 00:01:07,740 --> 00:01:10,960 Kalkulatu erdigunea Gaur egungo sub array. 26 00:01:10,960 --> 00:01:14,460 >> Balioa bila bazabiltza da array elementu horretan, gelditzeko. 27 00:01:14,460 --> 00:01:15,030 Aurkitu duzu. 28 00:01:15,030 --> 00:01:16,550 Hori handia. 29 00:01:16,550 --> 00:01:19,610 Bestela, helburua bada Zer da erdian baino gutxiago, 30 00:01:19,610 --> 00:01:23,430 beraz, ez dugu bilatzen ari balioa bada Ba ikusten duguna baino txikiagoa da, 31 00:01:23,430 --> 00:01:26,780 Prozesu hau errepikatu berriro, baina aldatu amaiera puntua, ordez 32 00:01:26,780 --> 00:01:29,300 original izatearen multzo osoa bete, 33 00:01:29,300 --> 00:01:34,110 besterik ezkerrera izan non begiratu besterik ez dugu. 34 00:01:34,110 --> 00:01:38,940 >> Bagenekien erdian izan ez bada ere, edo helburuaren erdian baino txikiagoa izan zen, 35 00:01:38,940 --> 00:01:42,210 eta beraz, existitu behar da, bada batere array existitzen, 36 00:01:42,210 --> 00:01:44,660 nonbait erdigunea ezkerreko. 37 00:01:44,660 --> 00:01:48,120 Eta beraz, array ezarri beharko dugu besterik ezkerreko kokapena 38 00:01:48,120 --> 00:01:51,145 erdigunea amaieran puntu berri gisa. 39 00:01:51,145 --> 00:01:53,770 Aitzitik, helburu bada Zer da erdian baino handiagoa, 40 00:01:53,770 --> 00:01:55,750 zehatza bera egiten dugu prozesua, baina horren ordez dugu 41 00:01:55,750 --> 00:01:59,520 Irteeran aldatu ahal besterik erdigunea eskubidea 42 00:01:59,520 --> 00:02:00,680 kalkulatzen besterik ez dugu. 43 00:02:00,680 --> 00:02:03,220 Eta orduan, prozesua hasten gara berriro. 44 00:02:03,220 --> 00:02:05,220 >> Dezagun Ikusteko honetan, OK? 45 00:02:05,220 --> 00:02:08,620 Beraz, ez da asko gertatzen da eta hemen da, baina hemen 15 elementuen array bat. 46 00:02:08,620 --> 00:02:11,400 Eta ari gara egon jarraipena joan a lot more stuff denbora honen. 47 00:02:11,400 --> 00:02:13,870 Beraz, bilaketa lineala ere, izan ginen besterik helburu zaintzearen. 48 00:02:13,870 --> 00:02:15,869 Baina une honetan egin nahi dugu arduratu non gauden 49 00:02:15,869 --> 00:02:18,480 begiratzen hasita, non ari ari gara gelditzen, 50 00:02:18,480 --> 00:02:21,876 eta zer da erdigunea Gaur egungo array. 51 00:02:21,876 --> 00:02:23,250 Hortaz, hona hemen bilaketa bitarra joan ginen. 52 00:02:23,250 --> 00:02:25,290 Nahiko askoz ona joan, lasai egongo gara? 53 00:02:25,290 --> 00:02:28,650 Besterik ez naiz behera jarri nahi dut azpitik hemen indizeak multzo bat. 54 00:02:28,650 --> 00:02:32,430 Hau da, funtsean, zer elementu Array hizketan ari garen. 55 00:02:32,430 --> 00:02:34,500 Bilaketa lineala, gara zaintzeko, zeren dugun bezala 56 00:02:34,500 --> 00:02:36,800 Badakizu zenbat behar elementu ari gainean errepikatzean dugu, 57 00:02:36,800 --> 00:02:40,010 baina ez ditu zaintzen dugu zer elementu Une gara begira. 58 00:02:40,010 --> 00:02:41,014 Bilaketa bitarra, egiten dugu. 59 00:02:41,014 --> 00:02:42,930 Eta beraz, horiek besterik ez dira Han gida txiki bat bezala. 60 00:02:42,930 --> 00:02:44,910 >> Beraz, hasi ahal izango dugu, ezta? 61 00:02:44,910 --> 00:02:46,240 Beno, ez da nahiko. 62 00:02:46,240 --> 00:02:48,160 Gogoratu zer esan dut bilaketa bitarra buruz? 63 00:02:48,160 --> 00:02:50,955 Ezin dugu ezer egingo batean Sailkatu array edo, bestela, 64 00:02:50,955 --> 00:02:55,820 ez gara hori bermatuz elementu edo balore jakin batzuk ez dira 65 00:02:55,820 --> 00:02:57,650 ustekabean izateaz baztertzea denean besterik ez dugu 66 00:02:57,650 --> 00:02:59,920 array erdia alde batetara utzi erabakitzeko. 67 00:02:59,920 --> 00:03:02,574 >> Beraz, bilaketa bitarra bat zapaldu da ordenatuko array bat izan behar duzu. 68 00:03:02,574 --> 00:03:05,240 Eta sailkatzeko edozein erabili ahal izango duzu hitz egin dugu algoritmoak 69 00:03:05,240 --> 00:03:06,700 you get to posizio horretara. 70 00:03:06,700 --> 00:03:10,370 Beraz, gaur egun, ez gara posizio bat, non ere bilaketa bitarra egin ahal izango dugu. 71 00:03:10,370 --> 00:03:12,560 >> Hargatik errepikatu prozesua pausoz pauso eta mantentzeko 72 00:03:12,560 --> 00:03:14,830 Zer ari da gertatzen joan gara pista. 73 00:03:14,830 --> 00:03:17,980 Beraz, lehenengo kalkulatu da egin behar dugu Gaur egungo array erdigunea. 74 00:03:17,980 --> 00:03:20,620 Beno, esan dugu ari gara, lehen guztiak, 19 balio du bila. 75 00:03:20,620 --> 00:03:22,290 19 zenbakira bilatzen saiatzen ari gara. 76 00:03:22,290 --> 00:03:25,380 Honen lehenengo elementua array da indizea zero kokatuta dago, 77 00:03:25,380 --> 00:03:28,880 eta horren azken elementua array da indizea 14 at dago. 78 00:03:28,880 --> 00:03:31,430 Eta beraz, hasieratik horiek eta azkenean deitu dugu. 79 00:03:31,430 --> 00:03:35,387 >> Beraz arabera erdigunea kalkulatzeko dugu 0 plus 14 2 banatuta gehituz; 80 00:03:35,387 --> 00:03:36,720 nahiko erraza erdigunea. 81 00:03:36,720 --> 00:03:40,190 Eta hori esan dezakegu erdigunea da orain 7. 82 00:03:40,190 --> 00:03:43,370 Beraz, 15 da zer bilatzen ari gara? 83 00:03:43,370 --> 00:03:43,940 Ez, ez da. 84 00:03:43,940 --> 00:03:45,270 Ari gara 19 bila. 85 00:03:45,270 --> 00:03:49,400 Baina badakigu 19 handiagoa zer aurkitu erdian gu baino. 86 00:03:49,400 --> 00:03:52,470 >> Beraz, zer egin ahal izango dugu Irteeran aldatu 87 00:03:52,470 --> 00:03:57,280 to besterik eskubidea izango erdigunea, eta errepikatu prozesua berriro. 88 00:03:57,280 --> 00:04:01,690 Eta noiz egiten dugu, orain esan dugun Irteeran berria array kokapena 8 da. 89 00:04:01,690 --> 00:04:07,220 Zer eraginkorrean dugu egin da bazterrera utzi 15 ezkerreko dena. 90 00:04:07,220 --> 00:04:09,570 Erdi Nik kendu dugu Arazoaren, eta orain, 91 00:04:09,570 --> 00:04:13,510 ordez bilatu beharrean gure array elementu 15 baino gehiago, 92 00:04:13,510 --> 00:04:15,610 7 gehiagoko bilatu beharko dugu. 93 00:04:15,610 --> 00:04:17,706 Beraz, 8 Irteeran berria da. 94 00:04:17,706 --> 00:04:19,600 14 amaieran puntua da oraindik. 95 00:04:19,600 --> 00:04:21,430 >> Eta orain, hori baino gehiago ere joaten gara. 96 00:04:21,430 --> 00:04:22,810 Erdigunea berria kalkulatu dugu. 97 00:04:22,810 --> 00:04:27,130 8 plus 14 22 da, 2 11 da banatuta. 98 00:04:27,130 --> 00:04:28,660 Hau da, zer bilatzen ari gara? 99 00:04:28,660 --> 00:04:30,110 Ez, ez da. 100 00:04:30,110 --> 00:04:32,930 Ari gara, hori da balio baten bila besterik zer aurkitu genuen baino gutxiago. 101 00:04:32,930 --> 00:04:34,721 Beraz, errepikatu egingo da prozesua berriro. 102 00:04:34,721 --> 00:04:38,280 Amaieran puntua aldatzen goaz besterik erdigunea ezkerreko izan. 103 00:04:38,280 --> 00:04:41,800 Beraz, amaieran puntu berria bihurtzen 10. 104 00:04:41,800 --> 00:04:44,780 Eta orain, horren zati bat bakarrik da array bidez ordenatzeko behar dugu. 105 00:04:44,780 --> 00:04:48,460 Beraz kendu orain dugu 12 15 elementuetako. 106 00:04:48,460 --> 00:04:51,550 Badakigu 19 baldin bada array batean badago, 107 00:04:51,550 --> 00:04:57,210 nonbait existitzen behar elementu arteko 8 eta 10 elementu kopurua. 108 00:04:57,210 --> 00:04:59,400 >> Beraz, erdigunea berria kalkulatu dugu berriro. 109 00:04:59,400 --> 00:05:02,900 8 plus 10 18 da, 2 9 da banatuta. 110 00:05:02,900 --> 00:05:05,074 Eta, kasu honetan, begiratu, helburu erdian dago. 111 00:05:05,074 --> 00:05:06,740 Zehazki zer bilatzen ari gara aurkitu dugu. 112 00:05:06,740 --> 00:05:07,780 Gelditu ahal izango dugu. 113 00:05:07,780 --> 00:05:10,561 Arrakastaz burutu dugu bilaketa bitarra bat. 114 00:05:10,561 --> 00:05:11,060 Ados. 115 00:05:11,060 --> 00:05:13,930 Beraz, algoritmo hau ezagutzen dugun lan egiten du xede da bada 116 00:05:13,930 --> 00:05:16,070 nonbait array barruan. 117 00:05:16,070 --> 00:05:19,060 Algoritmoa lan badu helburua ez da array? 118 00:05:19,060 --> 00:05:20,810 Beno, goazen hasi da berriro, eta oraingo honetan, 119 00:05:20,810 --> 00:05:23,380 ikus ditzagun elementu 16, ikusmen ikusi ahal izango dugu 120 00:05:23,380 --> 00:05:25,620 ez da existitzen lekutan array. 121 00:05:25,620 --> 00:05:27,110 >> Irteeran da berriro 0. 122 00:05:27,110 --> 00:05:28,590 Amaieran puntua da berriro 14. 123 00:05:28,590 --> 00:05:32,490 Horiek dira lehen indizeak eta osoa array azken elementuak. 124 00:05:32,490 --> 00:05:36,057 Eta besterik ez dugu prozesuan zehar joan beharko dugu ziren handik berriro, 16 aurkitu nahian, 125 00:05:36,057 --> 00:05:39,140 nahiz eta ikusmen arren, ezin dugu dagoeneko Esango ez da hori ez da izango. 126 00:05:39,140 --> 00:05:43,450 Nahi dugu ziur algoritmo hau egiteko izango da, hain zuzen ere, oraindik ere, nolabait ere, lan 127 00:05:43,450 --> 00:05:46,310 eta ez bakarrik utzi digu begizta infinitua bat trabatuta. 128 00:05:46,310 --> 00:05:48,190 >> Beraz, zein da urrats lehen? 129 00:05:48,190 --> 00:05:50,230 Kalkulatu erdigunea Gaur egungo array. 130 00:05:50,230 --> 00:05:52,790 Zer da erdigunea Gaur egungo array? 131 00:05:52,790 --> 00:05:54,410 Beno, 7, ezta? 132 00:05:54,410 --> 00:05:57,560 14 plus 0 2 banatuta 7 da. 133 00:05:57,560 --> 00:05:59,280 15 zer bilatzen ari gara? 134 00:05:59,280 --> 00:05:59,780 No. 135 00:05:59,780 --> 00:06:02,930 Nahiko hurbil, baina begira ari gara balio bat baino zertxobait handiagoa da. 136 00:06:02,930 --> 00:06:06,310 >> Beraz, badakigu dela joan izan ezerezetik 15 ezkerreko. 137 00:06:06,310 --> 00:06:08,540 Helburu baino handiagoa da zer erdigunea ere egin. 138 00:06:08,540 --> 00:06:12,450 Eta beraz, hasteko puntua berria ezarri dugu erdi-erdian eskubidea izan. 139 00:06:12,450 --> 00:06:16,130 Erdigunea da gaur egun 7, hain demagun the Irteeran berria 8 da. 140 00:06:16,130 --> 00:06:18,130 Eta zer eraginkorrean dugu Berriro egiten da bazterrera utzi 141 00:06:18,130 --> 00:06:21,150 the array osoan ezkerreko erdi. 142 00:06:21,150 --> 00:06:23,750 >> Orain, berriz diogu du prozesatu denbora gehiago. 143 00:06:23,750 --> 00:06:24,910 Kalkulatu erdigunea berria. 144 00:06:24,910 --> 00:06:29,350 8 plus 14 22 da, 2 11 da banatuta. 145 00:06:29,350 --> 00:06:31,060 23 zer bilatzen ari gara? 146 00:06:31,060 --> 00:06:31,870 Zoritxarrez, ez. 147 00:06:31,870 --> 00:06:34,930 Gaude balio bat bilatzen 23 baino gutxiago. 148 00:06:34,930 --> 00:06:37,850 Eta, beraz, kasu honetan, goazen amaieran puntua aldatzeko zuzena izateko 149 00:06:37,850 --> 00:06:40,035 uneko erdigunea ezkerreko. 150 00:06:40,035 --> 00:06:43,440 Egungo erdigunea 11 da, eta beraz, bukaera puntua berriak ezarri beharko dugu 151 00:06:43,440 --> 00:06:46,980 hurrengo denbora joan ginen 10 Prozesu honen bidez. 152 00:06:46,980 --> 00:06:48,660 >> Berriz ere, berriro prozesuan zehar joan ginen. 153 00:06:48,660 --> 00:06:49,640 Kalkulatu erdigunea. 154 00:06:49,640 --> 00:06:53,100 8 plus 10 2 banatuta 9 da. 155 00:06:53,100 --> 00:06:54,750 19 zer bilatzen ari gara? 156 00:06:54,750 --> 00:06:55,500 Zoritxarrez, ez. 157 00:06:55,500 --> 00:06:58,050 Oraindik ari gara bila Zenbaki bat baino gutxiago. 158 00:06:58,050 --> 00:07:02,060 Beraz, une honetan amaiera puntua aldatu egingo besterik erdigunea ezkerreko izan. 159 00:07:02,060 --> 00:07:05,532 Erdigunea da gaur egun 9 beraz, azken puntua 8 izango da. 160 00:07:05,532 --> 00:07:07,920 Eta orain, besterik bilatzen ari gara elementu array bakar batean. 161 00:07:07,920 --> 00:07:10,250 >> Zer da array honen erdigunea? 162 00:07:10,250 --> 00:07:13,459 Beno, hasten 8 at da, 8 amaitzen da, erdigunea 8 da. 163 00:07:13,459 --> 00:07:14,750 Hori da guk nahi? 164 00:07:14,750 --> 00:07:16,339 Ari gara 17k? 165 00:07:16,339 --> 00:07:17,380 Ez, 16. bilatzen ari gara. 166 00:07:17,380 --> 00:07:20,160 Beraz, badago sorta batean bazaude, nonbait existitu behar da 167 00:07:20,160 --> 00:07:21,935 non gaur egun gauden ezkerreko. 168 00:07:21,935 --> 00:07:23,060 Beraz, zer egin behar dugu joan? 169 00:07:23,060 --> 00:07:26,610 Beno, ezarri egingo dugu amaieran puntu besterik ez izan uneko erdigunea ezkerreko. 170 00:07:26,610 --> 00:07:29,055 Beraz, ez dugu azken puntua aldatu egingo 7ra. 171 00:07:29,055 --> 00:07:32,120 Ez zer besterik ikusten duzu Hemen gertatu zen, nahiz eta? 172 00:07:32,120 --> 00:07:33,370 Look up hemen orain. 173 00:07:33,370 --> 00:07:35,970 >> Start bukaera baino handiagoa da orain. 174 00:07:35,970 --> 00:07:39,620 Eraginkortasunez, bi muturrak gure array zeharkatu dute, 175 00:07:39,620 --> 00:07:42,252 eta Irteeran da orain amaieran puntua ondoren. 176 00:07:42,252 --> 00:07:43,960 Beno, hori ez da Edozein zentzurik, ezta? 177 00:07:43,960 --> 00:07:47,960 Beraz, orain, zer esan dezakegu dugu tamaina 0 array azpi dute. 178 00:07:47,960 --> 00:07:50,110 Eta behin goaz ahaztuak Puntu honetan, gaur egun ezin dugu 179 00:07:50,110 --> 00:07:53,940 elementu hori bermatzen 16 ez du array existitzen, 180 00:07:53,940 --> 00:07:56,280 Irteeran delako eta amaieran puntu zeharkatu dute. 181 00:07:56,280 --> 00:07:58,340 Eta, beraz, ez da han. 182 00:07:58,340 --> 00:08:01,340 Orain, nabarituko hori da apur bat the Irteeran eta amaiera baino ezberdinak 183 00:08:01,340 --> 00:08:02,900 puntu berdina izanik. 184 00:08:02,900 --> 00:08:05,030 Dugu izan balitz bila 17an, izango litzateke 185 00:08:05,030 --> 00:08:08,870 array, eta hasiera-puntua izan eta amaitzeko, azken iterazio duten puntua 186 00:08:08,870 --> 00:08:11,820 puntu horiek zeharkatu aurretik, aurkitu izana genuke 17 han. 187 00:08:11,820 --> 00:08:15,510 Besterik ez da, zeharkatuko dute, ahal dugun elementua ez du bermatzen 188 00:08:15,510 --> 00:08:17,180 array existitzen. 189 00:08:17,180 --> 00:08:20,260 >> Hargatik hartu en asko gutxiago bilaketa lineala baino urrats. 190 00:08:20,260 --> 00:08:23,250 Txarrenean ere, izan dugu zatitu n elementu zerrenda bat 191 00:08:23,250 --> 00:08:27,770 behin eta berriz erditik helburua bilatzen, bai delako helburu elementua 192 00:08:27,770 --> 00:08:33,110 nonbait izango da, azken batean zatiketa, edo ez du existitzen. 193 00:08:33,110 --> 00:08:37,830 Beraz, kasu txarrenean, izan dugu zatitu array du dakizu? 194 00:08:37,830 --> 00:08:40,510 N aldiz log; dugu arazoa moztu dute 195 00:08:40,510 --> 00:08:42,610 erdi aldiz kopuru jakin batean. 196 00:08:42,610 --> 00:08:45,160 Aldiz kopuru hori log n da. 197 00:08:45,160 --> 00:08:46,510 >> Zer da kasurik onenean? 198 00:08:46,510 --> 00:08:48,899 Beno, lehenengo aldiz dugu erdigunea kalkulatzeko, 199 00:08:48,899 --> 00:08:50,190 zer bilatzen ari gara aurkitzen dugu. 200 00:08:50,190 --> 00:08:52,150 Aurreko guztietan bilaketa bitarra adibide 201 00:08:52,150 --> 00:08:55,489 besterik ez dugu desagertu baino gehiago izan badugu bila elementua 15, 202 00:08:55,489 --> 00:08:57,030 berehala topatu ditugun litzateke. 203 00:08:57,030 --> 00:08:58,321 Hori oso hasiera-hasieratik izan zen. 204 00:08:58,321 --> 00:09:01,200 Hori izan zen erdigunea split batean lehen saiakera 205 00:09:01,200 --> 00:09:03,950 bilaketa bitarra zatiketa baten. 206 00:09:03,950 --> 00:09:06,350 >> Eta beraz txarrenean Kasu, bilaketa bitarra exekutatzen 207 00:09:06,350 --> 00:09:11,580 log n, hau da, nabarmen hobea Bilaketa lineala, txarrena kasuan baino. 208 00:09:11,580 --> 00:09:16,210 Kasurik onenean ere, binary Bilaketa-1 omega exekutatzen. 209 00:09:16,210 --> 00:09:18,990 Beraz, bilaketa bitarra asko da bilaketa lineala baino hobea, 210 00:09:18,990 --> 00:09:23,270 baina prozesua landu behar duzula sailkatuz, zure array lehenengo ahal duzun aurretik 211 00:09:23,270 --> 00:09:26,140 leverage bilaketa bitarra boterea. 212 00:09:26,140 --> 00:09:27,130 >> Naiz Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 Hau CS 50 da. 214 00:09:29,470 --> 00:09:31,070