1 00:00:00,000 --> 00:00:03,346 >> [MUSIK SPELA] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG LLOYD: Okej. 4 00:00:06,220 --> 00:00:08,140 Så binär sökning är en algoritm kan vi använda 5 00:00:08,140 --> 00:00:10,530 att hitta ett element inne i en matris. 6 00:00:10,530 --> 00:00:14,710 Till skillnad från linjär sökning, krävs det en särskilda villkor måste uppfyllas på förhand, 7 00:00:14,710 --> 00:00:19,020 men det är så mycket mer effektivt om detta villkor är faktiskt uppfyllda. 8 00:00:19,020 --> 00:00:20,470 >> Så vad är tanken här? 9 00:00:20,470 --> 00:00:21,780 Det är söndra och härska. 10 00:00:21,780 --> 00:00:25,100 Vi vill minska storleken på sökområdet med hälften varje gång 11 00:00:25,100 --> 00:00:27,240 i syfte att finna ett målnummer. 12 00:00:27,240 --> 00:00:29,520 Det är där detta villkor kommer in i bilden, men. 13 00:00:29,520 --> 00:00:32,740 Vi kan bara utnyttja kraften i eliminera hälften av elementen 14 00:00:32,740 --> 00:00:36,070 utan att ens titta på dem om arrayen sorteras. 15 00:00:36,070 --> 00:00:39,200 >> Om det är en komplett blandning upp, vi kan inte bara ur hand 16 00:00:39,200 --> 00:00:42,870 kassera hälften av elementen, eftersom vi vet inte vad vi ska kasta. 17 00:00:42,870 --> 00:00:45,624 Men om matrisen är sorterad, vi kan göra det, eftersom vi 18 00:00:45,624 --> 00:00:48,040 vet att allt till kvar av där vi för närvarande 19 00:00:48,040 --> 00:00:50,500 måste vara lägre än den värde som vi är närvarande på. 20 00:00:50,500 --> 00:00:52,300 Och allt till höger om där vi är 21 00:00:52,300 --> 00:00:55,040 måste vara större än det värde som Vi bläddrar i. 22 00:00:55,040 --> 00:00:58,710 >> Så vad är pseudo steg för binär sökning? 23 00:00:58,710 --> 00:01:02,310 Vi upprepar processen tills matris eller, som vi gå igenom, 24 00:01:02,310 --> 00:01:07,740 sub matriser, mindre bitar av den ursprungliga arrayen är av storlek 0. 25 00:01:07,740 --> 00:01:10,960 Beräkna mittpunkten av den aktuella underordnade uppsättningen. 26 00:01:10,960 --> 00:01:14,460 >> Om värdet du letar efter i denna del av gruppen, sluta. 27 00:01:14,460 --> 00:01:15,030 Du hittade det. 28 00:01:15,030 --> 00:01:16,550 Toppen. 29 00:01:16,550 --> 00:01:19,610 Annars, om målet är mindre än vad som finns i mitten, 30 00:01:19,610 --> 00:01:23,430 så om det värde vi letar för är lägre än vad vi ser, 31 00:01:23,430 --> 00:01:26,780 upprepa denna process igen, men ändra slutpunkten i stället 32 00:01:26,780 --> 00:01:29,300 av att vara den ursprungliga slutföra full uppsättning, 33 00:01:29,300 --> 00:01:34,110 vara precis till vänster var vi bara tittat. 34 00:01:34,110 --> 00:01:38,940 >> Vi visste att mitt var för högt, eller målet var mindre än i mitten, 35 00:01:38,940 --> 00:01:42,210 och så det måste föreligga, om den överhuvudtaget finns i arrayen, 36 00:01:42,210 --> 00:01:44,660 någonstans till vänster om mittpunkten. 37 00:01:44,660 --> 00:01:48,120 Och så vi får ställa in arrayen plats precis till vänster 38 00:01:48,120 --> 00:01:51,145 av mittpunkten som ny slutpunkt. 39 00:01:51,145 --> 00:01:53,770 Omvänt, om målet är större än vad som finns i mitten, 40 00:01:53,770 --> 00:01:55,750 Vi gör exakt samma process, men i stället vi 41 00:01:55,750 --> 00:01:59,520 ändra startpunkten att vara precis till höger om mittpunkten 42 00:01:59,520 --> 00:02:00,680 vi bara beräknas. 43 00:02:00,680 --> 00:02:03,220 Och sedan vi börja processen igen. 44 00:02:03,220 --> 00:02:05,220 >> Låt oss visualisera detta, OK? 45 00:02:05,220 --> 00:02:08,620 Så det händer mycket och här, men här är en samling av de 15 elementen. 46 00:02:08,620 --> 00:02:11,400 Och vi kommer att hålla reda av en mycket mer saker den här gången. 47 00:02:11,400 --> 00:02:13,870 Så i linjär sökning, var vi bara bry sig om ett mål. 48 00:02:13,870 --> 00:02:15,869 Men den här gången vill vi bryr sig om var är vi 49 00:02:15,869 --> 00:02:18,480 börjar se, där stannar vi ser, 50 00:02:18,480 --> 00:02:21,876 och vad är mittpunkten av den aktuella uppsättningen. 51 00:02:21,876 --> 00:02:23,250 Så här går vi med binär sökning. 52 00:02:23,250 --> 00:02:25,290 Vi är ganska mycket bra att gå, eller hur? 53 00:02:25,290 --> 00:02:28,650 Jag kommer bara att lägga ner nedan här en uppsättning index. 54 00:02:28,650 --> 00:02:32,430 Detta är i grunden precis vad elementet i matrisen vi pratar om. 55 00:02:32,430 --> 00:02:34,500 Med linjär sökning, vi vård, eftersom vi 56 00:02:34,500 --> 00:02:36,800 behöver veta hur många element vi iteration över, 57 00:02:36,800 --> 00:02:40,010 men vi egentligen inte bry sig om vad elementet vi bläddrar i. 58 00:02:40,010 --> 00:02:41,014 I binär sökning, gör vi. 59 00:02:41,014 --> 00:02:42,930 Och så de är bara där som en liten guide. 60 00:02:42,930 --> 00:02:44,910 >> Så vi kan börja, eller hur? 61 00:02:44,910 --> 00:02:46,240 Tja, inte riktigt. 62 00:02:46,240 --> 00:02:48,160 Kom ihåg vad jag sa om binär sökning? 63 00:02:48,160 --> 00:02:50,955 Vi kan inte göra det på ett osorterade array annars, 64 00:02:50,955 --> 00:02:55,820 vi inte garantera att den vissa element eller värden inte 65 00:02:55,820 --> 00:02:57,650 misstag bort när vi bara 66 00:02:57,650 --> 00:02:59,920 besluta att ignorera halv av arrayen. 67 00:02:59,920 --> 00:03:02,574 >> Så steg ett med binär sökning är att du måste ha en sorterade arrayen. 68 00:03:02,574 --> 00:03:05,240 Och du kan använda någon av sorteringen algoritmer vi har talat om 69 00:03:05,240 --> 00:03:06,700 för att få dig till den positionen. 70 00:03:06,700 --> 00:03:10,370 Så nu är vi i ett läge där vi kan utföra binär sökning. 71 00:03:10,370 --> 00:03:12,560 >> Så låt oss upprepa processen steg för steg och hålla 72 00:03:12,560 --> 00:03:14,830 koll på vad som händer när vi går. 73 00:03:14,830 --> 00:03:17,980 Så det första vi måste göra är att beräkna mittpunkten av den aktuella uppsättningen. 74 00:03:17,980 --> 00:03:20,620 Tja, ska vi säga att vi är först och allt efter värdet 19. 75 00:03:20,620 --> 00:03:22,290 Vi försöker hitta numret 19. 76 00:03:22,290 --> 00:03:25,380 Den första delen av detta matris är belägen på index noll, 77 00:03:25,380 --> 00:03:28,880 och den sista delen av detta array ligger på index 14. 78 00:03:28,880 --> 00:03:31,430 Och så vi kallar dem början och slut. 79 00:03:31,430 --> 00:03:35,387 >> Så vi beräknar mittpunkten av sätta 0 plus 14 dividerat med 2; 80 00:03:35,387 --> 00:03:36,720 ganska enkelt mittpunkt. 81 00:03:36,720 --> 00:03:40,190 Och vi kan säga att mittpunkten är nu 7. 82 00:03:40,190 --> 00:03:43,370 Så är 15 det vi letar efter? 83 00:03:43,370 --> 00:03:43,940 Nej det är det inte. 84 00:03:43,940 --> 00:03:45,270 Vi letar efter 19. 85 00:03:45,270 --> 00:03:49,400 Men vi vet att 19 är större än vad vi hittade i mitten. 86 00:03:49,400 --> 00:03:52,470 >> Så vad vi kan göra är ändra startpunkten 87 00:03:52,470 --> 00:03:57,280 vara precis till höger om den mittpunkt, och upprepa processen igen. 88 00:03:57,280 --> 00:04:01,690 Och när vi gör det, nu säger vi nya startpunkten är array plats 8. 89 00:04:01,690 --> 00:04:07,220 Vad vi har faktiskt gjort är ignoreras allt till vänster om 15. 90 00:04:07,220 --> 00:04:09,570 Vi har eliminerat hälften av problemet, och nu, 91 00:04:09,570 --> 00:04:13,510 i stället för att behöva söka över 15 element i vår samling, 92 00:04:13,510 --> 00:04:15,610 vi bara måste söka över 7. 93 00:04:15,610 --> 00:04:17,706 Så 8 är den nya startpunkten. 94 00:04:17,706 --> 00:04:19,600 14 är fortfarande slutpunkten. 95 00:04:19,600 --> 00:04:21,430 >> Och nu går vi över detta igen. 96 00:04:21,430 --> 00:04:22,810 Vi beräknar den nya mittpunkten. 97 00:04:22,810 --> 00:04:27,130 8 plus 14 är 22 dividerat med 2 är 11. 98 00:04:27,130 --> 00:04:28,660 Är detta vad vi letar efter? 99 00:04:28,660 --> 00:04:30,110 Nej det är det inte. 100 00:04:30,110 --> 00:04:32,930 Vi letar efter ett värde som är mindre än vad vi just hittat. 101 00:04:32,930 --> 00:04:34,721 Så vi kommer att upprepa processen igen. 102 00:04:34,721 --> 00:04:38,280 Vi kommer att ändra slutpunkten till vara precis till vänster om mittpunkten. 103 00:04:38,280 --> 00:04:41,800 Så den nya slutpunkten blir 10. 104 00:04:41,800 --> 00:04:44,780 Och nu, det är bara en del av arrayen vi måste gå igenom. 105 00:04:44,780 --> 00:04:48,460 Så har vi nu eliminerat 12 av de 15 elementen. 106 00:04:48,460 --> 00:04:51,550 Vi vet att om 19 existerar i arrayen, det 107 00:04:51,550 --> 00:04:57,210 måste finnas någonstans mellan elementet nummer 8 och elementnumret 10. 108 00:04:57,210 --> 00:04:59,400 >> Så vi beräkna den nya mittpunkten igen. 109 00:04:59,400 --> 00:05:02,900 8 plus 10 är 18 dividerat med 2 är 9. 110 00:05:02,900 --> 00:05:05,074 Och i detta fall, titta, den Målet är i mitten. 111 00:05:05,074 --> 00:05:06,740 Vi hittade precis vad vi letar efter. 112 00:05:06,740 --> 00:05:07,780 Vi kan stoppa. 113 00:05:07,780 --> 00:05:10,561 Vi avklarad en binär sökning. 114 00:05:10,561 --> 00:05:11,060 Okej. 115 00:05:11,060 --> 00:05:13,930 Så vi vet denna algoritm fungerar om målet är 116 00:05:13,930 --> 00:05:16,070 någonstans inne i matrisen. 117 00:05:16,070 --> 00:05:19,060 Gör detta algoritm arbete om målet är inte i arrayen? 118 00:05:19,060 --> 00:05:20,810 Nåväl, låt oss börja den igen, och den här gången, 119 00:05:20,810 --> 00:05:23,380 låt oss titta för elementet 16, som visuellt kan vi se 120 00:05:23,380 --> 00:05:25,620 existerar inte någonstans i matrisen. 121 00:05:25,620 --> 00:05:27,110 >> Startpunkten är återigen 0. 122 00:05:27,110 --> 00:05:28,590 Slutpunkten är återigen 14. 123 00:05:28,590 --> 00:05:32,490 De är indexen för den första och sista element i den kompletta arrayen. 124 00:05:32,490 --> 00:05:36,057 Och vi kommer att gå igenom processen vi bara gick igenom igen, försöka hitta 16, 125 00:05:36,057 --> 00:05:39,140 trots att visuellt kan vi redan tala om att det inte kommer att vara där. 126 00:05:39,140 --> 00:05:43,450 Vi vill bara se till att denna algoritm kommer i själva verket fortfarande att fungera på något sätt 127 00:05:43,450 --> 00:05:46,310 och inte bara lämna oss fastnat i en oändlig loop. 128 00:05:46,310 --> 00:05:48,190 >> Så vad är steget först? 129 00:05:48,190 --> 00:05:50,230 Beräkna mittpunkten av den aktuella uppsättningen. 130 00:05:50,230 --> 00:05:52,790 Vad är mittpunkten av den aktuella uppsättningen? 131 00:05:52,790 --> 00:05:54,410 Tja, det är 7, eller hur? 132 00:05:54,410 --> 00:05:57,560 14 plus 0 delat med 2 är 7. 133 00:05:57,560 --> 00:05:59,280 Är 15 det vi letar efter? 134 00:05:59,280 --> 00:05:59,780 Nej. 135 00:05:59,780 --> 00:06:02,930 Det är ganska nära, men vi letar för ett värde något större än så. 136 00:06:02,930 --> 00:06:06,310 >> Så vet vi att det kommer att ingenstans till vänster om 15. 137 00:06:06,310 --> 00:06:08,540 Målet är större än vad som finns i mittpunkten. 138 00:06:08,540 --> 00:06:12,450 Och så sätter vi den nya startpunkten till vara precis till höger om mitten. 139 00:06:12,450 --> 00:06:16,130 Mittpunkten är för närvarande 7, så låt oss säga den nya startpunkten är 8. 140 00:06:16,130 --> 00:06:18,130 Och vad vi har på ett effektivt sätt gjort igen ignoreras 141 00:06:18,130 --> 00:06:21,150 hela vänstra halv av arrayen. 142 00:06:21,150 --> 00:06:23,750 >> Nu, vi upprepa bearbeta en gång. 143 00:06:23,750 --> 00:06:24,910 Beräkna den nya mittpunkten. 144 00:06:24,910 --> 00:06:29,350 8 plus 14 är 22 dividerat med 2 är 11. 145 00:06:29,350 --> 00:06:31,060 Är 23 det vi letar efter? 146 00:06:31,060 --> 00:06:31,870 Tyvärr inte. 147 00:06:31,870 --> 00:06:34,930 Vi letar efter ett värde som är mindre än 23. 148 00:06:34,930 --> 00:06:37,850 Och så i det här fallet, kommer vi att ändra slutpunkten vara bara 149 00:06:37,850 --> 00:06:40,035 till vänster om den aktuella mittpunkten. 150 00:06:40,035 --> 00:06:43,440 Den nuvarande mittpunkt är 11, och så vi får ställa in den nya slutpunkten 151 00:06:43,440 --> 00:06:46,980 för nästa gång vi åker genom denna process till 10. 152 00:06:46,980 --> 00:06:48,660 >> Återigen, vi går igenom processen igen. 153 00:06:48,660 --> 00:06:49,640 Beräkna mittpunkten. 154 00:06:49,640 --> 00:06:53,100 8 plus 10 delat med två är 9. 155 00:06:53,100 --> 00:06:54,750 Är 19 det vi letar efter? 156 00:06:54,750 --> 00:06:55,500 Tyvärr inte. 157 00:06:55,500 --> 00:06:58,050 Vi letar fortfarande efter ett antal mindre än så. 158 00:06:58,050 --> 00:07:02,060 Så vi kommer att ändra slutpunkten den här gången vara precis till vänster om mittpunkten. 159 00:07:02,060 --> 00:07:05,532 Mittpunkten är för närvarande 9, så slutpunkten kommer att vara 8. 160 00:07:05,532 --> 00:07:07,920 Och nu är vi bara ute vid en enda elementgrupp. 161 00:07:07,920 --> 00:07:10,250 >> Vad är mittpunkten i denna samling? 162 00:07:10,250 --> 00:07:13,459 Tja, börjar det på 8, det slutar vid 8, är mittpunkten 8. 163 00:07:13,459 --> 00:07:14,750 Är det vad vi letar efter? 164 00:07:14,750 --> 00:07:16,339 Söker vi 17? 165 00:07:16,339 --> 00:07:17,380 Nej, vi letar efter 16. 166 00:07:17,380 --> 00:07:20,160 Så om den finns i arrayen, Det måste finnas någonstans 167 00:07:20,160 --> 00:07:21,935 till vänster om där vi är idag. 168 00:07:21,935 --> 00:07:23,060 Så vad ska vi göra? 169 00:07:23,060 --> 00:07:26,610 Tja, vi ställa in slutpunkten vara bara till vänster om den aktuella mittpunkten. 170 00:07:26,610 --> 00:07:29,055 Så vi kommer att ändra slutpunkten till 7. 171 00:07:29,055 --> 00:07:32,120 Ser du vad som just hände här, men? 172 00:07:32,120 --> 00:07:33,370 Slå upp här nu. 173 00:07:33,370 --> 00:07:35,970 >> Start är nu större än slutet. 174 00:07:35,970 --> 00:07:39,620 I själva verket de två ändarna av vår samling har passerat, 175 00:07:39,620 --> 00:07:42,252 och startpunkten är nu efter slutpunkten. 176 00:07:42,252 --> 00:07:43,960 Tja, gör det inte vettigt, eller hur? 177 00:07:43,960 --> 00:07:47,960 Så nu, vad vi kan säga är att vi har en sub uppsättning av storlek 0. 178 00:07:47,960 --> 00:07:50,110 Och när vi kommit till denna punkt, kan vi nu 179 00:07:50,110 --> 00:07:53,940 garantera att elementet 16 existerar inte i arrayen, 180 00:07:53,940 --> 00:07:56,280 eftersom startpunkten och slutpunkt har passerat. 181 00:07:56,280 --> 00:07:58,340 Och så är det inte det. 182 00:07:58,340 --> 00:08:01,340 Nu märker att detta är något annorlunda än startpunkten och slut 183 00:08:01,340 --> 00:08:02,900 punkt är densamma. 184 00:08:02,900 --> 00:08:05,030 Om vi ​​hade letat för 17, skulle det ha 185 00:08:05,030 --> 00:08:08,870 varit i arrayen, och startpunkten och slutpunkt den sista iterationen 186 00:08:08,870 --> 00:08:11,820 innan dessa punkter i kors, vi skulle ha funnit 17 där. 187 00:08:11,820 --> 00:08:15,510 Det är bara när de passerar att vi kan garantera att elementet inte 188 00:08:15,510 --> 00:08:17,180 existerar i arrayen. 189 00:08:17,180 --> 00:08:20,260 >> Så låt oss ta en mycket färre steg än linjär sökning. 190 00:08:20,260 --> 00:08:23,250 I värsta fall, hade vi att dela upp en lista med n element 191 00:08:23,250 --> 00:08:27,770 upprepade gånger i halv att hitta målet, antingen för att målelementet 192 00:08:27,770 --> 00:08:33,110 kommer att vara någonstans i den sista division, eller om den inte finns alls. 193 00:08:33,110 --> 00:08:37,830 Så i värsta fall måste vi dela upp array-- vet du? 194 00:08:37,830 --> 00:08:40,510 Logga av n gånger; vi måste skära problemet 195 00:08:40,510 --> 00:08:42,610 i halv ett visst antal gånger. 196 00:08:42,610 --> 00:08:45,160 Det antal gånger är log n. 197 00:08:45,160 --> 00:08:46,510 >> Vad är det bästa scenariot? 198 00:08:46,510 --> 00:08:48,899 Tja, första gången vi beräkna mittpunkten, 199 00:08:48,899 --> 00:08:50,190 finner vi vad vi letar efter. 200 00:08:50,190 --> 00:08:52,150 I alla tidigare exempel på binär sökning 201 00:08:52,150 --> 00:08:55,489 Vi har precis gått över, om vi hade letat efter elementet 15, 202 00:08:55,489 --> 00:08:57,030 vi skulle ha funnit det omedelbart. 203 00:08:57,030 --> 00:08:58,321 Det var i början. 204 00:08:58,321 --> 00:09:01,200 Det var mittpunkten av det första försöket vid en split 205 00:09:01,200 --> 00:09:03,950 av en division i binär sökning. 206 00:09:03,950 --> 00:09:06,350 >> Och så i värsta fall binär sökning körs 207 00:09:06,350 --> 00:09:11,580 i log n, som är väsentligt bättre än linjär sökning, i värsta fall. 208 00:09:11,580 --> 00:09:16,210 I bästa fall, binär sökning körs i omega 1. 209 00:09:16,210 --> 00:09:18,990 Så binär sökning är en mycket bättre än linjär sökning, 210 00:09:18,990 --> 00:09:23,270 men du måste ta itu med processen för sortering arrayen först innan du kan 211 00:09:23,270 --> 00:09:26,140 utnyttja kraften i binär sökning. 212 00:09:26,140 --> 00:09:27,130 >> Jag är Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 Detta är CS 50. 214 00:09:29,470 --> 00:09:31,070