1 00:00:00,000 --> 00:00:03,346 >> [Musiikkia] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG Lloyd: Selvä. 4 00:00:06,220 --> 00:00:08,140 Joten binary haku on algoritmi voimme käyttää 5 00:00:08,140 --> 00:00:10,530 löytää elementin sisällä array. 6 00:00:10,530 --> 00:00:14,710 Toisin kuin lineaarinen haku, se vaatii erityisedellytystä täytyttävä etukäteen, 7 00:00:14,710 --> 00:00:19,020 mutta se on niin paljon tehokkaampaa, jos tämä edellytys on, itse asiassa, täyty. 8 00:00:19,020 --> 00:00:20,470 >> Niin mitä idea täällä? 9 00:00:20,470 --> 00:00:21,780 se on hajota ja hallitse. 10 00:00:21,780 --> 00:00:25,100 Haluamme pienentää hakualuetta puoleen joka kerta 11 00:00:25,100 --> 00:00:27,240 jotta löydettäisiin tavoite numero. 12 00:00:27,240 --> 00:00:29,520 Tässä on, että ehto tulee pelata, vaikka. 13 00:00:29,520 --> 00:00:32,740 Voimme vain hyödyntää valtaa poistamalla puolet elementit 14 00:00:32,740 --> 00:00:36,070 katsomatta edes ne, jos jono on lajiteltu. 15 00:00:36,070 --> 00:00:39,200 >> Jos se on täydellinen sekoitus ylös, Emme voi vain käsistä 16 00:00:39,200 --> 00:00:42,870 hävitä puolet elementtejä, koska emme tiedä, mitä me poisheittäminen. 17 00:00:42,870 --> 00:00:45,624 Mutta jos array lajitellaan, Voimme tehdä niin, koska me 18 00:00:45,624 --> 00:00:48,040 tietävät, että kaiken vasemmalle, missä me tällä hetkellä olemme 19 00:00:48,040 --> 00:00:50,500 on oltava pienempi kuin arvo olemme tällä hetkellä. 20 00:00:50,500 --> 00:00:52,300 Ja kaiken oikeus missä olemme 21 00:00:52,300 --> 00:00:55,040 on oltava suurempi kuin arvo me tarkastelee parhaillaan. 22 00:00:55,040 --> 00:00:58,710 >> Niin mitä pseudokoodina vaiheet binary haku? 23 00:00:58,710 --> 00:01:02,310 Toistamme tätä, kunnes array tai, kuten me käymme eteenpäin, 24 00:01:02,310 --> 00:01:07,740 sub paneelit pienempiä paloja alkuperäinen joukko, on koko 0. 25 00:01:07,740 --> 00:01:10,960 Laske puoliväli Nykyisen osa array. 26 00:01:10,960 --> 00:01:14,460 >> Jos arvo etsit on että elementti array, lopeta. 27 00:01:14,460 --> 00:01:15,030 Löysit sen. 28 00:01:15,030 --> 00:01:16,550 Sepä hienoa. 29 00:01:16,550 --> 00:01:19,610 Muuten, jos tavoite on vähemmän kuin mitä keskellä, 30 00:01:19,610 --> 00:01:23,430 joten jos arvo etsimme sillä on alempi kuin mitä näemme, 31 00:01:23,430 --> 00:01:26,780 toista tämä prosessi uudelleen, mutta muuttaa päätepiste, vaan 32 00:01:26,780 --> 00:01:29,300 olemisen alkuperäisen täydellinen täyden valikoiman, 33 00:01:29,300 --> 00:01:34,110 olla vain vasemmalla missä me vain katsoi. 34 00:01:34,110 --> 00:01:38,940 >> Tiesimme, että keskellä oli liian korkea, tai kohde oli alle keskellä, 35 00:01:38,940 --> 00:01:42,210 ja niin se on olemassa, jos se olemassa lainkaan array, 36 00:01:42,210 --> 00:01:44,660 jonnekin vasemmalla keskipisteen. 37 00:01:44,660 --> 00:01:48,120 Ja niin me asettaa array sijainti vain vasemmalla 38 00:01:48,120 --> 00:01:51,145 keskipisteen uudeksi päätepiste. 39 00:01:51,145 --> 00:01:53,770 Sitä vastoin, jos tavoite on suurempi kuin mitä keskellä, 40 00:01:53,770 --> 00:01:55,750 teemme täsmälleen sama prosessi, mutta sen sijaan me 41 00:01:55,750 --> 00:01:59,520 muuttaa aloituspisteen olla juuri oikealla keskipisteen 42 00:01:59,520 --> 00:02:00,680 me vain lasketaan. 43 00:02:00,680 --> 00:02:03,220 Ja sitten, aloitamme uudelleen. 44 00:02:03,220 --> 00:02:05,220 >> Katsotaanpa visualisoida, OK? 45 00:02:05,220 --> 00:02:08,620 Joten siellä on paljon menossa ja täällä, mutta tässä on joukko 15 elementtejä. 46 00:02:08,620 --> 00:02:11,400 Ja aiomme olla pitää kirjaa paljon enemmän juttuja tällä kertaa. 47 00:02:11,400 --> 00:02:13,870 Joten lineaarinen haku, olimme vain välittäminen kohde. 48 00:02:13,870 --> 00:02:15,869 Mutta tällä kertaa haluamme välitä missä olemme 49 00:02:15,869 --> 00:02:18,480 alkaa näyttää, missä pysähdyimme etsimässä, 50 00:02:18,480 --> 00:02:21,876 ja mitä keskipisteen nykyisen taulukon. 51 00:02:21,876 --> 00:02:23,250 Joten tässä sitä mennään binary haku. 52 00:02:23,250 --> 00:02:25,290 Olemme melko paljon hyvä mennä, eikö? 53 00:02:25,290 --> 00:02:28,650 Olen juuri menossa laittaa alas Alla täällä joukko indeksejä. 54 00:02:28,650 --> 00:02:32,430 Tämä on pohjimmiltaan vain mitä elementti array puhumme. 55 00:02:32,430 --> 00:02:34,500 Lineaarinen haku, me care, koska me 56 00:02:34,500 --> 00:02:36,800 täytyy tietää, kuinka monta elementit olemme iteroimalla yli, 57 00:02:36,800 --> 00:02:40,010 mutta emme oikeastaan ​​välitä mitä elementti me tarkastelee parhaillaan. 58 00:02:40,010 --> 00:02:41,014 Binary haku, teemme. 59 00:02:41,014 --> 00:02:42,930 Ja niin ne ovat vain siellä pieni opas. 60 00:02:42,930 --> 00:02:44,910 >> Jotta voimme aloittaa, eikö? 61 00:02:44,910 --> 00:02:46,240 No, ei aivan. 62 00:02:46,240 --> 00:02:48,160 Muista mitä sanoin noin binary haku? 63 00:02:48,160 --> 00:02:50,955 Emme voi tehdä sitä lajittelemattomien array tai muuten, 64 00:02:50,955 --> 00:02:55,820 emme takaa, että tiettyjä osia tai arvot eivät ole 65 00:02:55,820 --> 00:02:57,650 tahattomat hävittää kun me vain 66 00:02:57,650 --> 00:02:59,920 päättää ohittaa puolet jono. 67 00:02:59,920 --> 00:03:02,574 >> Astu siis yksi binary haku on sinulla on lajiteltu array. 68 00:03:02,574 --> 00:03:05,240 Ja voit käyttää mitä tahansa lajittelu algoritmit olemme puhuneet 69 00:03:05,240 --> 00:03:06,700 saada sinut että asentoon. 70 00:03:06,700 --> 00:03:10,370 Joten nyt olemme asemassa, jossa voimme tehdä binary haku. 71 00:03:10,370 --> 00:03:12,560 >> Joten toistaa prosessi askel askeleelta ja pitää 72 00:03:12,560 --> 00:03:14,830 seurata, mitä tapahtuu kun kuljemme. 73 00:03:14,830 --> 00:03:17,980 Joten ensimmäinen meidän täytyy tehdä, on laskea keskipiste nykyisen taulukon. 74 00:03:17,980 --> 00:03:20,620 No, me sanomme olemme, ensimmäinen kaikki, etsii arvon 19. 75 00:03:20,620 --> 00:03:22,290 Yritämme löytää numero 19. 76 00:03:22,290 --> 00:03:25,380 Ensimmäinen osa tätä array sijaitsee indeksi nolla, 77 00:03:25,380 --> 00:03:28,880 ja viimeinen osa tätä array sijaitsee olevan 14. 78 00:03:28,880 --> 00:03:31,430 Ja niin soitamme ne alun ja lopun. 79 00:03:31,430 --> 00:03:35,387 >> Joten laskemme keskipisteen lisäämällä 0 plus 14 jaettuna 2; 80 00:03:35,387 --> 00:03:36,720 melko yksinkertainen keskipiste. 81 00:03:36,720 --> 00:03:40,190 Ja voimme sanoa, että keskipiste on nyt 7. 82 00:03:40,190 --> 00:03:43,370 Joten on 15, mitä etsimme? 83 00:03:43,370 --> 00:03:43,940 Ei se ei ole. 84 00:03:43,940 --> 00:03:45,270 Etsimme 19. 85 00:03:45,270 --> 00:03:49,400 Mutta me tiedämme, että 19 on suurempi kuin mitä löysimme keskellä. 86 00:03:49,400 --> 00:03:52,470 >> Joten mitä voimme tehdä on muuttaa aloituspiste 87 00:03:52,470 --> 00:03:57,280 olla juuri oikealla keskipiste, ja toista prosessi uudestaan. 88 00:03:57,280 --> 00:04:01,690 Ja kun teemme sen, sanomme nyt uusi alkupiste on array paikka 8. 89 00:04:01,690 --> 00:04:07,220 Mitä olemme hoitaa tehokkaasti on huomiotta kaikki vasemmalle 15. 90 00:04:07,220 --> 00:04:09,570 Olemme eliminoitu puoli Ongelman, ja nyt, 91 00:04:09,570 --> 00:04:13,510 sen sijaan, etsiä yli 15 elementtiä meidän array, 92 00:04:13,510 --> 00:04:15,610 meillä on vain etsiä yli 7. 93 00:04:15,610 --> 00:04:17,706 Joten 8 on uusi aloituspiste. 94 00:04:17,706 --> 00:04:19,600 14 on edelleen päätepiste. 95 00:04:19,600 --> 00:04:21,430 >> Ja nyt, mennään tänä uudelleen. 96 00:04:21,430 --> 00:04:22,810 Laskemme uusi keskipiste. 97 00:04:22,810 --> 00:04:27,130 8 plus 14 on 22, jaettuna 2 on 11. 98 00:04:27,130 --> 00:04:28,660 Tätäkö me etsimme? 99 00:04:28,660 --> 00:04:30,110 Ei se ei ole. 100 00:04:30,110 --> 00:04:32,930 Etsimme arvo, joka on vähemmän kuin mitä me juuri löytänyt. 101 00:04:32,930 --> 00:04:34,721 Joten aiomme toistaa uudelleen. 102 00:04:34,721 --> 00:04:38,280 Aiomme muuttaa päätepiste olla vain vasemmalla keskipisteen. 103 00:04:38,280 --> 00:04:41,800 Joten uusi päätepiste tulee 10. 104 00:04:41,800 --> 00:04:44,780 Ja nyt, se on vain osa array olemme lajitella kautta. 105 00:04:44,780 --> 00:04:48,460 Joten olemme nyt poistettu 12 15 elementtiä. 106 00:04:48,460 --> 00:04:51,550 Tiedämme, että jos 19 olemassa jono, se 107 00:04:51,550 --> 00:04:57,210 on oltava olemassa jonnekin elementin numero 8 ja elementin numero 10. 108 00:04:57,210 --> 00:04:59,400 >> Joten laskemme uuden keskipisteen uudelleen. 109 00:04:59,400 --> 00:05:02,900 8 + 10 on 18, jaettuna 2 on 9. 110 00:05:02,900 --> 00:05:05,074 Ja tässä tapauksessa, katso, tavoite on keskellä. 111 00:05:05,074 --> 00:05:06,740 Löysimme juuri sitä, mitä etsit. 112 00:05:06,740 --> 00:05:07,780 Voimme lopettaa. 113 00:05:07,780 --> 00:05:10,561 Olemme onnistuneesti binäärihaku. 114 00:05:10,561 --> 00:05:11,060 Selvä. 115 00:05:11,060 --> 00:05:13,930 Joten me tiedämme tämän algoritmi toimii jos tavoite on 116 00:05:13,930 --> 00:05:16,070 jonnekin sisällä jono. 117 00:05:16,070 --> 00:05:19,060 Onko tämä algoritmi työ jos tavoite ei ole array? 118 00:05:19,060 --> 00:05:20,810 No, aloitetaan se uudelleen, ja tällä kertaa, 119 00:05:20,810 --> 00:05:23,380 Katsotaanpa elementille 16, joka visuaalisesti voimme nähdä 120 00:05:23,380 --> 00:05:25,620 ei ole missään pakassa. 121 00:05:25,620 --> 00:05:27,110 >> Alkupiste on jälleen 0. 122 00:05:27,110 --> 00:05:28,590 Päätepiste on jälleen 14. 123 00:05:28,590 --> 00:05:32,490 Ne ovat indeksejä ensimmäisen ja viimeinen elementit täydellinen valikoima. 124 00:05:32,490 --> 00:05:36,057 Ja me mennä läpi me vain meni läpi uudelleen, yrittää löytää 16, 125 00:05:36,057 --> 00:05:39,140 vaikka visuaalisesti, voimme jo sanoa, että se ei aio olla siellä. 126 00:05:39,140 --> 00:05:43,450 Haluamme vain varmistaa tämä algoritmi tulee itse asiassa vielä työtä jollain tavalla 127 00:05:43,450 --> 00:05:46,310 ja ei jätä meitä jumissa päättymättömään silmukkaan. 128 00:05:46,310 --> 00:05:48,190 >> Niin mitä askel ensimmäinen? 129 00:05:48,190 --> 00:05:50,230 Laske puoliväli nykyisen taulukon. 130 00:05:50,230 --> 00:05:52,790 Mikä keskipisteen Nykyisen array? 131 00:05:52,790 --> 00:05:54,410 No, se on 7, eikö? 132 00:05:54,410 --> 00:05:57,560 14 plus 0 jaettuna 2 on 7. 133 00:05:57,560 --> 00:05:59,280 On 15, mitä etsimme? 134 00:05:59,280 --> 00:05:59,780 Ei. 135 00:05:59,780 --> 00:06:02,930 Se on melko lähellä, mutta etsimme joiden arvo hieman suurempi kuin. 136 00:06:02,930 --> 00:06:06,310 >> Joten me tiedämme, että se tulee olla missään vasemmalle 15. 137 00:06:06,310 --> 00:06:08,540 Tavoitteena on suurempi kuin mitä on keskipiste. 138 00:06:08,540 --> 00:06:12,450 Ja niin asetamme uusia aloituspiste olla juuri oikealla keskellä. 139 00:06:12,450 --> 00:06:16,130 Keskipiste on tällä hetkellä 7, joten sanokaamme uusi alkupiste on 8. 140 00:06:16,130 --> 00:06:18,130 Ja mitä olemme tehokkaasti tehdä uudelleen ohitetaan 141 00:06:18,130 --> 00:06:21,150 koko vasen puoli jono. 142 00:06:21,150 --> 00:06:23,750 >> Nyt toistamme käsitellä vielä kerran. 143 00:06:23,750 --> 00:06:24,910 Laske uusi keskipiste. 144 00:06:24,910 --> 00:06:29,350 8 plus 14 on 22, jaettuna 2 on 11. 145 00:06:29,350 --> 00:06:31,060 On 23, mitä etsimme? 146 00:06:31,060 --> 00:06:31,870 Valitettavasti ei. 147 00:06:31,870 --> 00:06:34,930 Etsimme arvo joka on vähemmän kuin 23. 148 00:06:34,930 --> 00:06:37,850 Ja niin tässä tapauksessa, menemme muuttaa päätepiste on vain 149 00:06:37,850 --> 00:06:40,035 vasemmalle nykyisen keskipisteen. 150 00:06:40,035 --> 00:06:43,440 Nykyinen keskipiste on 11, ja niin me asettaa uusi päätepiste 151 00:06:43,440 --> 00:06:46,980 Seuraavan kerran menemme Tämän prosessin kautta 10. 152 00:06:46,980 --> 00:06:48,660 >> Jälleen me mennä läpi uudelleen. 153 00:06:48,660 --> 00:06:49,640 Laske keskipiste. 154 00:06:49,640 --> 00:06:53,100 8 plus 10 jaettuna 2 on 9. 155 00:06:53,100 --> 00:06:54,750 On 19, mitä etsimme? 156 00:06:54,750 --> 00:06:55,500 Valitettavasti ei. 157 00:06:55,500 --> 00:06:58,050 Olemme vielä etsimässä numero pienempi. 158 00:06:58,050 --> 00:07:02,060 Niin me muuttaa päätepiste tällä kertaa olla vain vasemmalla keskipisteen. 159 00:07:02,060 --> 00:07:05,532 Keskipiste on tällä hetkellä 9, joten päätepiste on 8. 160 00:07:05,532 --> 00:07:07,920 Ja nyt, me vain etsimässä yhdellä alkiotaulukon. 161 00:07:07,920 --> 00:07:10,250 >> Mikä keskipiste tämän array? 162 00:07:10,250 --> 00:07:13,459 No, se alkaa 8, se päättyy 8, keskipiste on 8. 163 00:07:13,459 --> 00:07:14,750 Sitäkö etsimme? 164 00:07:14,750 --> 00:07:16,339 Me etsimme 17? 165 00:07:16,339 --> 00:07:17,380 Ei, me etsimme 16. 166 00:07:17,380 --> 00:07:20,160 Joten jos se on olemassa joukko, sen on olemassa jonnekin 167 00:07:20,160 --> 00:07:21,935 vasemmalle, missä me nyt olemme. 168 00:07:21,935 --> 00:07:23,060 Joten mitä me teemme? 169 00:07:23,060 --> 00:07:26,610 No, me asettaa päätepiste on vain vasemmalle nykyisen keskipisteen. 170 00:07:26,610 --> 00:07:29,055 Niin me muuttaa päätepiste 7. 171 00:07:29,055 --> 00:07:32,120 Ymmärrätkö, mitä vain täällä on tapahtunut, vaikka? 172 00:07:32,120 --> 00:07:33,370 Katso täällä nyt. 173 00:07:33,370 --> 00:07:35,970 >> Start on nyt suurempi kuin lopussa. 174 00:07:35,970 --> 00:07:39,620 Tehokkaasti, kaksi päätä meidän array ovat ylittäneet, 175 00:07:39,620 --> 00:07:42,252 ja alkupiste on nyt kun päätepiste. 176 00:07:42,252 --> 00:07:43,960 No, joka ei mitään järkeä, eikö? 177 00:07:43,960 --> 00:07:47,960 Joten nyt, mitä voimme sanoa on meidän on osa joukko koko 0. 178 00:07:47,960 --> 00:07:50,110 Ja kun me mennyt Tässä vaiheessa voimme nyt 179 00:07:50,110 --> 00:07:53,940 taata, että elementti 16 ei ole olemassa jono, 180 00:07:53,940 --> 00:07:56,280 koska alkupiste ja päätepiste ovat ristissä. 181 00:07:56,280 --> 00:07:58,340 Ja niin se ei ole siellä. 182 00:07:58,340 --> 00:08:01,340 Nyt, huomaa, että tämä on hieman eri kuin alkupiste ja loppu 183 00:08:01,340 --> 00:08:02,900 kohta on sama. 184 00:08:02,900 --> 00:08:05,030 Jos olisimme olleet etsimässä 17, se olisi 185 00:08:05,030 --> 00:08:08,870 ollut array, ja aloituspiste ja loppupiste että viime iterointia 186 00:08:08,870 --> 00:08:11,820 ennen näitä pistettä ristissä, olisimme löytyi 17 siellä. 187 00:08:11,820 --> 00:08:15,510 Vasta kun he ylittävät että voimme taata, että elementti ei 188 00:08:15,510 --> 00:08:17,180 olemassa jono. 189 00:08:17,180 --> 00:08:20,260 >> Joten vie paljon vähemmän vaiheet kuin lineaarinen haku. 190 00:08:20,260 --> 00:08:23,250 Pahimmassa tapauksessa, meillä oli jakaa luettelon n alkion 191 00:08:23,250 --> 00:08:27,770 toistuvasti puolet löytää kohde, joko siksi kohdistuselementti 192 00:08:27,770 --> 00:08:33,110 on jossain viimeisen alueeseen tai sitä ei ole lainkaan. 193 00:08:33,110 --> 00:08:37,830 Joten pahimmassa tapauksessa meidän on jakaa array-- tiedät? 194 00:08:37,830 --> 00:08:40,510 Loki n kertaa; me on leikata ongelma 195 00:08:40,510 --> 00:08:42,610 puolessa tietyn määrän kertoja. 196 00:08:42,610 --> 00:08:45,160 Että monta kertaa on log n. 197 00:08:45,160 --> 00:08:46,510 >> Mikä on parhaassa tapauksessa? 198 00:08:46,510 --> 00:08:48,899 No, ensimmäinen kerta laskea keskipiste, 199 00:08:48,899 --> 00:08:50,190 löydämme mitä etsimme. 200 00:08:50,190 --> 00:08:52,150 Kaikissa edellinen esimerkkejä binary haku 201 00:08:52,150 --> 00:08:55,489 Olemme juuri mennyt yli, jos meillä olisi etsinyt elementti 15, 202 00:08:55,489 --> 00:08:57,030 olisimme havainneet, että heti. 203 00:08:57,030 --> 00:08:58,321 Se oli aivan alussa. 204 00:08:58,321 --> 00:09:01,200 Se oli keskipiste ensimmäinen yritys split 205 00:09:01,200 --> 00:09:03,950 of jako binary haku. 206 00:09:03,950 --> 00:09:06,350 >> Ja niin pahimmassa tapauksessa, binary haku toimii 207 00:09:06,350 --> 00:09:11,580 in log n, joka on olennaisesti parempi kuin lineaarinen haku, pahimmassa tapauksessa. 208 00:09:11,580 --> 00:09:16,210 Parhaassa tapauksessa binary haku toimii omega 1. 209 00:09:16,210 --> 00:09:18,990 Joten binary haku on paljon parempi kuin lineaarinen haku, 210 00:09:18,990 --> 00:09:23,270 mutta sinun täytyy käsitellä prosessi lajittelu array ennen kuin voit 211 00:09:23,270 --> 00:09:26,140 hyödyntää valtaa binäärihaku. 212 00:09:26,140 --> 00:09:27,130 >> Olen Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 Tämä on CS 50. 214 00:09:29,470 --> 00:09:31,070