1
00:00:00,000 --> 00:00:03,346
>> [MUSIC JOC]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Bine.

4
00:00:06,220 --> 00:00:08,140
Deci căutare binară este un
algoritm putem folosi

5
00:00:08,140 --> 00:00:10,530
pentru a găsi un element în interiorul unui tablou.

6
00:00:10,530 --> 00:00:14,710
Spre deosebire de căutare liniară, este nevoie de o
condiție specială trebuie îndeplinite în prealabil,

7
00:00:14,710 --> 00:00:19,020
dar este atât de mult mai eficientă dacă
această condiție este, de fapt, sa întâlnit.

8
00:00:19,020 --> 00:00:20,470
>> Deci, ce este ideea aici?

9
00:00:20,470 --> 00:00:21,780
e divide și cuceri.

10
00:00:21,780 --> 00:00:25,100
Vrem pentru a reduce dimensiunea de
zona de căutare de jumătate de fiecare dată

11
00:00:25,100 --> 00:00:27,240
în scopul de a găsi un număr de țintă.

12
00:00:27,240 --> 00:00:29,520
Acest lucru este în cazul în care această condiție
intră în joc, deși.

13
00:00:29,520 --> 00:00:32,740
Putem parghie numai puterea de
eliminând jumătate din elementele

14
00:00:32,740 --> 00:00:36,070
fără măcar să se uite la
le în cazul în care matrice este sortat.

15
00:00:36,070 --> 00:00:39,200
>> Daca este un amestec complet în sus,
nu putem doar din mână

16
00:00:39,200 --> 00:00:42,870
aruncați jumătate din elementele, deoarece
nu știm ce ne aruncarea.

17
00:00:42,870 --> 00:00:45,624
Dar dacă matrice este sortat,
putem face asta, pentru că am

18
00:00:45,624 --> 00:00:48,040
Știu că totul la
stânga de unde în prezent ne aflăm

19
00:00:48,040 --> 00:00:50,500
trebuie să fie mai mică decât
Valoarea suntem în prezent la.

20
00:00:50,500 --> 00:00:52,300
Si totul la
drept de unde suntem

21
00:00:52,300 --> 00:00:55,040
trebuie să fie mai mare decât valoarea
ne caută în prezent.

22
00:00:55,040 --> 00:00:58,710
>> Deci, ce-i Pseudocodul
pași pentru căutare binare?

23
00:00:58,710 --> 00:01:02,310
Repetăm ​​acest proces până când
matrice sau, așa cum vom proceda prin,

24
00:01:02,310 --> 00:01:07,740
sub tablouri, bucăți mai mici de
matrice originală, este de dimensiuni 0.

25
00:01:07,740 --> 00:01:10,960
Calculați punctul de mijloc
Sub matrice curent.

26
00:01:10,960 --> 00:01:14,460
>> În cazul în care valoarea ce căutați este
prin aceea că elementul de matrice, opri.

27
00:01:14,460 --> 00:01:15,030
Ai găsit.

28
00:01:15,030 --> 00:01:16,550
Grozav.

29
00:01:16,550 --> 00:01:19,610
În caz contrar, în cazul în care obiectivul este
mai puțin de ceea ce este la mijloc,

30
00:01:19,610 --> 00:01:23,430
Deci, dacă valoarea pe care o căutați
este mai mică decât ceea ce vedem,

31
00:01:23,430 --> 00:01:26,780
repeta acest proces din nou, dar
schimba punctul de final, în loc

32
00:01:26,780 --> 00:01:29,300
de a fi original
finaliza gamă completă,

33
00:01:29,300 --> 00:01:34,110
să fie doar la stânga
de unde ne-am uitat.

34
00:01:34,110 --> 00:01:38,940
>> Stiam ca mijloc era prea mare,
sau ținta a fost mai mică decât la mijloc,

35
00:01:38,940 --> 00:01:42,210
și așa trebuie să existe, în cazul în care
există la toate în matrice,

36
00:01:42,210 --> 00:01:44,660
undeva în stânga punctul de mijloc.

37
00:01:44,660 --> 00:01:48,120
Și astfel vom stabili matrice
locație doar la stânga

38
00:01:48,120 --> 00:01:51,145
din punctul de mijloc ca noul punct final.

39
00:01:51,145 --> 00:01:53,770
În schimb, în ​​cazul în care obiectivul este
mai mare decât ceea ce este la mijloc,

40
00:01:53,770 --> 00:01:55,750
facem exact același
proces, dar în schimb am

41
00:01:55,750 --> 00:01:59,520
a schimba punctul de pornire pentru a fi
doar la dreptul de punctul de mijloc

42
00:01:59,520 --> 00:02:00,680
ne-am calculat.

43
00:02:00,680 --> 00:02:03,220
Și apoi, vom începe din nou procesul.

44
00:02:03,220 --> 00:02:05,220
>> Să vizualiza acest, bine?

45
00:02:05,220 --> 00:02:08,620
Deci, există o mulțime întâmplă și aici,
dar aici este o serie de 15 elemente.

46
00:02:08,620 --> 00:02:11,400
Și am de gând să fie urmărirea
de mult mai multe lucruri de data asta.

47
00:02:11,400 --> 00:02:13,870
Deci, în căutarea liniară, am fost
doar pese o țintă.

48
00:02:13,870 --> 00:02:15,869
Dar de data aceasta vrem să
pasă de unde suntem

49
00:02:15,869 --> 00:02:18,480
începe să arate, în cazul în care
ne-am oprit în căutarea,

50
00:02:18,480 --> 00:02:21,876
și ceea ce este punctul de mijloc
de matrice curent.

51
00:02:21,876 --> 00:02:23,250
Deci, aici vom merge cu căutare binară.

52
00:02:23,250 --> 00:02:25,290
Suntem destul de mult bun pentru a merge, nu?

53
00:02:25,290 --> 00:02:28,650
Mă duc pentru a pune în jos
de mai jos aici un set de indici.

54
00:02:28,650 --> 00:02:32,430
Aceasta este de fapt doar ceea ce element de
de matrice vorbim despre.

55
00:02:32,430 --> 00:02:34,500
Cu căutare liniară, am
îngrijire, în măsura în care ne

56
00:02:34,500 --> 00:02:36,800
trebuie să știe cât de multe
Elemente ne iterarea peste,

57
00:02:36,800 --> 00:02:40,010
dar nu-mi pasă de fapt ce
Element ne caută în prezent.

58
00:02:40,010 --> 00:02:41,014
În căutare binară, facem.

59
00:02:41,014 --> 00:02:42,930
Și așa acestea sunt doar
acolo ca un mic ghid.

60
00:02:42,930 --> 00:02:44,910
>> Astfel încât să putem începe, nu?

61
00:02:44,910 --> 00:02:46,240
Ei bine, nu chiar.

62
00:02:46,240 --> 00:02:48,160
Amintiți-vă ce am spus
despre căutarea binar?

63
00:02:48,160 --> 00:02:50,955
Noi nu putem face acest lucru pe o
matrice nesortate sau altceva,

64
00:02:50,955 --> 00:02:55,820
nu suntem garantarea faptului că
anumite elemente sau valori nu sunt

65
00:02:55,820 --> 00:02:57,650
fiind accidental
aruncată când ne-am

66
00:02:57,650 --> 00:02:59,920
decide să ignore jumătate din matrice.

67
00:02:59,920 --> 00:03:02,574
>> Deci, pas cu unul de căutare binară
este că trebuie să aibă o gamă sortate.

68
00:03:02,574 --> 00:03:05,240
Și vă puteți folosi oricare din sortarea
algoritmi am vorbit despre

69
00:03:05,240 --> 00:03:06,700
pentru a ajunge la această poziție.

70
00:03:06,700 --> 00:03:10,370
Deci, acum, suntem într-o poziție în care
putem efectua căutare binară.

71
00:03:10,370 --> 00:03:12,560
>> Deci, haideți să repetați procesul de
pas cu pas și să păstreze

72
00:03:12,560 --> 00:03:14,830
cont de ceea ce se intampla ca mergem.

73
00:03:14,830 --> 00:03:17,980
Deci, primul trebuie să facem este calcula
punctul de mijloc al matrice curent.

74
00:03:17,980 --> 00:03:20,620
Ei bine, vom spune că suntem, în primul
toate, în căutarea pentru valoarea 19.

75
00:03:20,620 --> 00:03:22,290
Încercăm să găsim numărul 19.

76
00:03:22,290 --> 00:03:25,380
Primul element al acestui
matrice este situat la index de zero,

77
00:03:25,380 --> 00:03:28,880
și ultimul element al acestei
matrice este situat la index 14.

78
00:03:28,880 --> 00:03:31,430
Și astfel vom suna cele de început și sfârșit.

79
00:03:31,430 --> 00:03:35,387
>> Așa că am calcula punctul de mijloc de
adăugarea 0 plus 14 împărțit la 2;

80
00:03:35,387 --> 00:03:36,720
punctul de mijloc destul de simplă.

81
00:03:36,720 --> 00:03:40,190
Și putem spune că
punctul de mijloc este acum 7.

82
00:03:40,190 --> 00:03:43,370
Deci, este de 15 ceea ce căutăm?

83
00:03:43,370 --> 00:03:43,940
Nu, nu este.

84
00:03:43,940 --> 00:03:45,270
Căutăm 19.

85
00:03:45,270 --> 00:03:49,400
Dar noi știm că 19 este mai mare
decât ceea ce am găsit la mijloc.

86
00:03:49,400 --> 00:03:52,470
>> Deci, ce putem face este
schimba punctul de start

87
00:03:52,470 --> 00:03:57,280
să fie doar pentru a dreapta
punctul de mijloc, și repetați din nou procesul.

88
00:03:57,280 --> 00:04:01,690
Și când facem asta, spunem acum
nou punct de plecare este matrice locație 8.

89
00:04:01,690 --> 00:04:07,220
Ce am făcut în mod eficient este
totul ignorat în partea stângă a 15.

90
00:04:07,220 --> 00:04:09,570
Am eliminat jumătate
a problemei, iar acum,

91
00:04:09,570 --> 00:04:13,510
în loc de a avea pentru a căuta
peste 15 elemente în oferta noastră,

92
00:04:13,510 --> 00:04:15,610
avem doar pentru a căuta peste 7.

93
00:04:15,610 --> 00:04:17,706
Deci 8 este noul punct de pornire.

94
00:04:17,706 --> 00:04:19,600
14 este în continuare punctul final.

95
00:04:19,600 --> 00:04:21,430
>> Și acum, ne-am trece peste asta din nou.

96
00:04:21,430 --> 00:04:22,810
Se calculează noul mijloc.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 este 22, împărțit la 2 este 11.

98
00:04:27,130 --> 00:04:28,660
Este aceasta ceea ce căutăm?

99
00:04:28,660 --> 00:04:30,110
Nu, nu este.

100
00:04:30,110 --> 00:04:32,930
Căutăm o valoare care este
mai puțin de ceea ce am găsit.

101
00:04:32,930 --> 00:04:34,721
Așa că am de gând să repet
procesul din nou.

102
00:04:34,721 --> 00:04:38,280
Vom schimba punctul final la
fie doar la stânga de punctul de mijloc.

103
00:04:38,280 --> 00:04:41,800
Deci noul punct final devine 10.

104
00:04:41,800 --> 00:04:44,780
Și acum, asta e doar o parte a
matrice avem pentru a sorta prin.

105
00:04:44,780 --> 00:04:48,460
Deci, am eliminat acum
12 din cele 15 elemente.

106
00:04:48,460 --> 00:04:51,550
Știm că, dacă 19
există în matrice, se

107
00:04:51,550 --> 00:04:57,210
trebuie să existe undeva între elementul
numărul 8 și numărul 10 element de.

108
00:04:57,210 --> 00:04:59,400
>> Deci, vom calcula din nou noul mijloc.

109
00:04:59,400 --> 00:05:02,900
8 plus 10 este 18, împărțit la 2 este 9.

110
00:05:02,900 --> 00:05:05,074
Și în acest caz, uite,
țintă este la mijloc.

111
00:05:05,074 --> 00:05:06,740
Am gasit exact ceea ce căutăm.

112
00:05:06,740 --> 00:05:07,780
Ne putem opri.

113
00:05:07,780 --> 00:05:10,561
Am finalizat cu succes
o căutare binară.

114
00:05:10,561 --> 00:05:11,060
In regula.

115
00:05:11,060 --> 00:05:13,930
Deci, noi știm acest algoritm
funcționează în cazul în care obiectivul este

116
00:05:13,930 --> 00:05:16,070
undeva în interiorul matrice.

117
00:05:16,070 --> 00:05:19,060
Face acest lucru în cazul în care algoritm
obiectivul nu este in matrice?

118
00:05:19,060 --> 00:05:20,810
Ei bine, hai să înceapă
din nou, și de această dată,

119
00:05:20,810 --> 00:05:23,380
să ne uităm pentru elementul
16, care vizual putem vedea

120
00:05:23,380 --> 00:05:25,620
nu există nicăieri în matrice.

121
00:05:25,620 --> 00:05:27,110
>> Punctul de pornire este din nou 0.

122
00:05:27,110 --> 00:05:28,590
Punctul final este din nou 14.

123
00:05:28,590 --> 00:05:32,490
Acestea sunt indicii ale primului și
ultimele elemente ale tabloului complet.

124
00:05:32,490 --> 00:05:36,057
Și vom merge prin procesul de ne-am
a trecut prin din nou, încercând să găsească 16,

125
00:05:36,057 --> 00:05:39,140
chiar dacă vizual, putem deja
spune că nu va fi acolo.

126
00:05:39,140 --> 00:05:43,450
Vrem doar să vă asigurați acest algoritm
va, de fapt, încă de lucru într-un fel

127
00:05:43,450 --> 00:05:46,310
și nu doar ne lase
blocat într-o buclă infinită.

128
00:05:46,310 --> 00:05:48,190
>> Deci, ce este pas prima?

129
00:05:48,190 --> 00:05:50,230
Calculați punctul de mijloc
de matrice curent.

130
00:05:50,230 --> 00:05:52,790
Care este punctul de mijloc
de matrice curent?

131
00:05:52,790 --> 00:05:54,410
Ei bine, e 7, nu?

132
00:05:54,410 --> 00:05:57,560
14 plus 0 împărțit la 2 este 7.

133
00:05:57,560 --> 00:05:59,280
Este de 15 ceea ce căutăm?

134
00:05:59,280 --> 00:05:59,780
Nu.

135
00:05:59,780 --> 00:06:02,930
E destul de aproape, dar căutăm
pentru o valoare puțin mai mare decât cea.

136
00:06:02,930 --> 00:06:06,310
>> Deci, știm că o să
fi nicăieri la stânga de 15.

137
00:06:06,310 --> 00:06:08,540
Ținta este mai mare de
ceea ce este în punctul de mijloc.

138
00:06:08,540 --> 00:06:12,450
Și astfel ne-am stabilit noul punct de pornire pentru
fie doar la dreptul de mijloc.

139
00:06:12,450 --> 00:06:16,130
Punctul de mijloc este în prezent 7, așa
să spunem noi punctul de pornire este de 8.

140
00:06:16,130 --> 00:06:18,130
Și ceea ce am în mod eficient
făcut din nou este ignorată

141
00:06:18,130 --> 00:06:21,150
întregul jumătatea stângă a șirului.

142
00:06:21,150 --> 00:06:23,750
>> Acum, ne-am repeta
procesa încă o dată.

143
00:06:23,750 --> 00:06:24,910
Calculați noul mijloc.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 este 22, împărțit la 2 este 11.

145
00:06:29,350 --> 00:06:31,060
Este de 23 ceea ce căutăm?

146
00:06:31,060 --> 00:06:31,870
Din păcate nu.

147
00:06:31,870 --> 00:06:34,930
Căutăm o valoare
care este mai mică de 23.

148
00:06:34,930 --> 00:06:37,850
Și astfel, în acest caz, vom
pentru a schimba punctul final să fie doar

149
00:06:37,850 --> 00:06:40,035
la stânga punctului de mijloc curent.

150
00:06:40,035 --> 00:06:43,440
Actualul mijloc este de 11, și
asa ca vom stabili noul punct final

151
00:06:43,440 --> 00:06:46,980
pentru data viitoare vom merge
prin acest proces la 10.

152
00:06:46,980 --> 00:06:48,660
>> Din nou, vom merge prin procesul din nou.

153
00:06:48,660 --> 00:06:49,640
Calculați punctul de mijloc.

154
00:06:49,640 --> 00:06:53,100
8 plus 10 împărțit la 2 este 9.

155
00:06:53,100 --> 00:06:54,750
Este ceea ce 19 căutăm?

156
00:06:54,750 --> 00:06:55,500
Din păcate nu.

157
00:06:55,500 --> 00:06:58,050
Suntem încă în căutarea pentru
un număr mai mic decât cel.

158
00:06:58,050 --> 00:07:02,060
Deci, vom schimba punctul final de această dată
să fie doar la stânga de punctul de mijloc.

159
00:07:02,060 --> 00:07:05,532
Punctul de mijloc este în prezent 9,
astfel încât punctul final va fi de 8.

160
00:07:05,532 --> 00:07:07,920
Și acum, suntem în căutarea doar
la un singur element de matrice.

161
00:07:07,920 --> 00:07:10,250
>> Care este punctul de mijloc al acestui tablou?

162
00:07:10,250 --> 00:07:13,459
Ei bine, aceasta începe la 8, ea
se termină la 8, punctul de mijloc este de 8.

163
00:07:13,459 --> 00:07:14,750
Este că ceea ce căutăm?

164
00:07:14,750 --> 00:07:16,339
Căutăm 17?

165
00:07:16,339 --> 00:07:17,380
Nu, suntem în căutarea pentru 16.

166
00:07:17,380 --> 00:07:20,160
Deci, dacă există în matrice,
trebuie să existe undeva

167
00:07:20,160 --> 00:07:21,935
în partea stângă a în cazul în care în prezent ne aflăm.

168
00:07:21,935 --> 00:07:23,060
Deci, ce ne facem?

169
00:07:23,060 --> 00:07:26,610
Ei bine, vom stabili punctul final să fie doar
la stânga punctului de mijloc curent.

170
00:07:26,610 --> 00:07:29,055
Deci, vom schimba punctul final la 7.

171
00:07:29,055 --> 00:07:32,120
Vedeți ce doar
sa întâmplat aici, deși?

172
00:07:32,120 --> 00:07:33,370
Uită-te aici, acum.

173
00:07:33,370 --> 00:07:35,970
>> Start este acum mai mare decât la sfârșitul.

174
00:07:35,970 --> 00:07:39,620
Efectiv, cele două capete
de oferta noastră au trecut,

175
00:07:39,620 --> 00:07:42,252
și punctul de pornire este
acum, după punctul final.

176
00:07:42,252 --> 00:07:43,960
Ei bine, asta nu
face nici un sens, nu?

177
00:07:43,960 --> 00:07:47,960
Deci, acum, ceea ce putem spune este că
au o gamă de dimensiuni sub 0.

178
00:07:47,960 --> 00:07:50,110
Și odată ce suntem ajuns la
acest punct, putem acum

179
00:07:50,110 --> 00:07:53,940
garantează că elementul 16
nu există în matrice,

180
00:07:53,940 --> 00:07:56,280
deoarece punctul de pornire
și punctul final au trecut.

181
00:07:56,280 --> 00:07:58,340
Și așa că nu e acolo.

182
00:07:58,340 --> 00:08:01,340
Acum, observați că acest lucru este ușor
diferit de punctul de început și de sfârșit

183
00:08:01,340 --> 00:08:02,900
punctul fiind același.

184
00:08:02,900 --> 00:08:05,030
Dacă am fi fost în căutarea
pentru 17, aceasta ar trebui

185
00:08:05,030 --> 00:08:08,870
fost în matrice, și punctul de start
și punctul final al acestei ultime repetare

186
00:08:08,870 --> 00:08:11,820
înainte de aceste puncte trecut,
am fi găsit acolo 17.

187
00:08:11,820 --> 00:08:15,510
Este doar atunci când acestea trec pe care putem
garanta că elementul nu

188
00:08:15,510 --> 00:08:17,180
există în matrice.

189
00:08:17,180 --> 00:08:20,260
>> Deci, haideți să aruncăm o mulțime mai
pași decât căutarea liniară.

190
00:08:20,260 --> 00:08:23,250
În cel mai rău caz, am avut
să împartă o listă de n elemente

191
00:08:23,250 --> 00:08:27,770
în mod repetat, în jumătate pentru a găsi țintă,
fie din cauză că elementul țintă

192
00:08:27,770 --> 00:08:33,110
va fi undeva în ultimul
divizare, sau nu există deloc.

193
00:08:33,110 --> 00:08:37,830
Deci, în cel mai rău caz, trebuie să ne
împărțit de array-- știi?

194
00:08:37,830 --> 00:08:40,510
Log de n ori; noi
trebuie să taie problema

195
00:08:40,510 --> 00:08:42,610
în jumătate un anumit număr de ori.

196
00:08:42,610 --> 00:08:45,160
Acest număr de ori este log n.

197
00:08:45,160 --> 00:08:46,510
>> Care este cel mai bun caz?

198
00:08:46,510 --> 00:08:48,899
Ei bine, prima dată WE
calcula punctul de mijloc,

199
00:08:48,899 --> 00:08:50,190
găsim ceea ce căutăm.

200
00:08:50,190 --> 00:08:52,150
În toate precedent
exemple de căutare binară

201
00:08:52,150 --> 00:08:55,489
tocmai am trecut peste, dacă am avea
căutat pentru elementul 15,

202
00:08:55,489 --> 00:08:57,030
am fi descoperit că imediat.

203
00:08:57,030 --> 00:08:58,321
Asta a fost la început.

204
00:08:58,321 --> 00:09:01,200
Acesta a fost punctul de mijloc al
prima încercare de o fracțiune de

205
00:09:01,200 --> 00:09:03,950
de o divizie în căutare binară.

206
00:09:03,950 --> 00:09:06,350
>> Și astfel în cel mai rău
caz, căutare binară ruleaza

207
00:09:06,350 --> 00:09:11,580
în jurnalul n, care este substanțial mai bine
decât căutarea liniară, în cel mai rău caz.

208
00:09:11,580 --> 00:09:16,210
În cel mai bun caz, binar
căutare ruleaza in omega de 1.

209
00:09:16,210 --> 00:09:18,990
Deci binar de căutare este mult
mai bine decât căutarea liniară,

210
00:09:18,990 --> 00:09:23,270
dar trebuie să se ocupe de procesul de
sortare matrice dumneavoastră înainte de a putea

211
00:09:23,270 --> 00:09:26,140
pârghie de putere de căutare binară.

212
00:09:26,140 --> 00:09:27,130
>> Sunt Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Aceasta este CS 50.

214
00:09:29,470 --> 00:09:31,070