1
00:00:00,000 --> 00:00:03,346
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

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

4
00:00:06,220 --> 00:00:08,140
Quindi ricerca binaria è un
algoritmo possiamo usare

5
00:00:08,140 --> 00:00:10,530
trovare un elemento all'interno di una matrice.

6
00:00:10,530 --> 00:00:14,710
Diversamente ricerca lineare, richiede un
condizione particolare essere soddisfatta in anticipo,

7
00:00:14,710 --> 00:00:19,020
ma è così molto più efficiente se
tale condizione, infatti, incontrato.

8
00:00:19,020 --> 00:00:20,470
>> Allora, qual è l'idea qui?

9
00:00:20,470 --> 00:00:21,780
è divide et impera.

10
00:00:21,780 --> 00:00:25,100
Vogliamo ridurre le dimensioni di
l'area di ricerca della metà ogni volta

11
00:00:25,100 --> 00:00:27,240
al fine di trovare un numero di destinazione.

12
00:00:27,240 --> 00:00:29,520
È qui che tale condizione
entra in gioco, però.

13
00:00:29,520 --> 00:00:32,740
Possiamo solo sfruttare la potenza di
eliminando metà degli elementi

14
00:00:32,740 --> 00:00:36,070
senza neanche guardare
loro se l'array vengono ordinati.

15
00:00:36,070 --> 00:00:39,200
>> Se si tratta di un mix completo up,
non possiamo solo di mano

16
00:00:39,200 --> 00:00:42,870
scartare metà degli elementi, perché
non sappiamo cosa stiamo scartando.

17
00:00:42,870 --> 00:00:45,624
Ma se l'array è ordinato,
possiamo farlo, perché noi

18
00:00:45,624 --> 00:00:48,040
sapere che tutto il
sinistra di dove ci troviamo attualmente

19
00:00:48,040 --> 00:00:50,500
deve essere inferiore alla
valore che siamo attualmente a.

20
00:00:50,500 --> 00:00:52,300
E tutto al
destra di dove siamo

21
00:00:52,300 --> 00:00:55,040
deve essere maggiore del valore
al momento stiamo guardando.

22
00:00:55,040 --> 00:00:58,710
>> Allora qual è il pseudocodice
passi per la ricerca binaria?

23
00:00:58,710 --> 00:01:02,310
Ripetiamo questo processo fino a quando la
array o, come si procede attraverso,

24
00:01:02,310 --> 00:01:07,740
array sub, piccoli pezzi di
la matrice originale, è di dimensioni 0.

25
00:01:07,740 --> 00:01:10,960
Calcolare il punto medio
dell'array sottopagina corrente.

26
00:01:10,960 --> 00:01:14,460
>> Se il valore che stai cercando è
in tale elemento dell'array, stop.

27
00:01:14,460 --> 00:01:15,030
L'hai trovato.

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

29
00:01:16,550 --> 00:01:19,610
Altrimenti, se il bersaglio è
meno di ciò che è al centro,

30
00:01:19,610 --> 00:01:23,430
così se il valore che stiamo cercando
per è inferiore a quello che si vede,

31
00:01:23,430 --> 00:01:26,780
ripetere questo processo, ma
modificare il punto finale, invece

32
00:01:26,780 --> 00:01:29,300
di essere l'originale
completare gamma completa,

33
00:01:29,300 --> 00:01:34,110
essere appena a sinistra
di cui abbiamo appena guardato.

34
00:01:34,110 --> 00:01:38,940
>> Sapevamo che il mezzo era troppo alto,
o l'obiettivo era meno di mezzo,

35
00:01:38,940 --> 00:01:42,210
e quindi deve esistere, se
esiste affatto nella matrice,

36
00:01:42,210 --> 00:01:44,660
posto alla sinistra del punto medio.

37
00:01:44,660 --> 00:01:48,120
E così imposteremo l'array
posizione appena a sinistra

38
00:01:48,120 --> 00:01:51,145
del punto medio come nuovo punto finale.

39
00:01:51,145 --> 00:01:53,770
Viceversa, se il bersaglio è
maggiore di quello che è in mezzo,

40
00:01:53,770 --> 00:01:55,750
noi facciamo la stessa esatta
processo, ma invece abbiamo

41
00:01:55,750 --> 00:01:59,520
modificare il punto iniziale di essere
subito a destra del punto medio

42
00:01:59,520 --> 00:02:00,680
abbiamo appena calcolato.

43
00:02:00,680 --> 00:02:03,220
E poi, si comincia di nuovo il processo.

44
00:02:03,220 --> 00:02:05,220
>> Cerchiamo di visualizzare questo, OK?

45
00:02:05,220 --> 00:02:08,620
Quindi c'è un sacco di cose e qui,
ma qui è un array dei 15 elementi.

46
00:02:08,620 --> 00:02:11,400
E stiamo andando a tenere traccia
di molte più cose questa volta.

47
00:02:11,400 --> 00:02:13,870
Quindi, in ricerca lineare, eravamo
solo preoccuparsi di un bersaglio.

48
00:02:13,870 --> 00:02:15,869
Ma questa volta vogliamo
preoccupano dove siamo

49
00:02:15,869 --> 00:02:18,480
cominciando a guardare, dove
ci fermiamo alla ricerca,

50
00:02:18,480 --> 00:02:21,876
e qual è il punto medio
dell'array corrente.

51
00:02:21,876 --> 00:02:23,250
Quindi qui si va con ricerca binaria.

52
00:02:23,250 --> 00:02:25,290
Siamo più o meno bene ad andare, giusto?

53
00:02:25,290 --> 00:02:28,650
Sto solo andando a mettere giù
sotto qui un insieme di indici.

54
00:02:28,650 --> 00:02:32,430
Questo è fondamentalmente solo quale elemento
della matrice di cui stiamo parlando.

55
00:02:32,430 --> 00:02:34,500
Con ricerca lineare, abbiamo
cura, in quanto ci

56
00:02:34,500 --> 00:02:36,800
bisogno di sapere quanti
Elementi stiamo iterare su,

57
00:02:36,800 --> 00:02:40,010
ma in realtà non importa cosa
elemento momento stiamo guardando.

58
00:02:40,010 --> 00:02:41,014
Alla ricerca binaria, che facciamo.

59
00:02:41,014 --> 00:02:42,930
E così questi sono solo
lì come una piccola guida.

60
00:02:42,930 --> 00:02:44,910
>> Così possiamo iniziare, giusto?

61
00:02:44,910 --> 00:02:46,240
Beh, non proprio.

62
00:02:46,240 --> 00:02:48,160
Ricordate ciò che ho detto
su ricerca binaria?

63
00:02:48,160 --> 00:02:50,955
Non possiamo farlo su un
matrice indifferenziati oppure,

64
00:02:50,955 --> 00:02:55,820
non stiamo garantendo che il
alcuni elementi o valori non sono

65
00:02:55,820 --> 00:02:57,650
accidentale
scartato quando abbiamo appena

66
00:02:57,650 --> 00:02:59,920
decidere di ignorare metà dell'array.

67
00:02:59,920 --> 00:03:02,574
>> Così passo uno con ricerca binaria
è devi avere un array ordinato.

68
00:03:02,574 --> 00:03:05,240
Ed è possibile utilizzare uno dei smistamento
algoritmi di cui abbiamo parlato

69
00:03:05,240 --> 00:03:06,700
per arrivare a quella posizione.

70
00:03:06,700 --> 00:03:10,370
Così ora, siamo in una posizione in cui
possiamo eseguire la ricerca binaria.

71
00:03:10,370 --> 00:03:12,560
>> Quindi cerchiamo di ripetere il processo
passo dopo passo e mantenere

72
00:03:12,560 --> 00:03:14,830
traccia di quello che sta accadendo, come andiamo.

73
00:03:14,830 --> 00:03:17,980
Quindi la prima abbiamo bisogno di fare è calcolare
il punto medio della matrice corrente.

74
00:03:17,980 --> 00:03:20,620
Bene, diremo che siamo, prima di
tutto, alla ricerca per il valore 19.

75
00:03:20,620 --> 00:03:22,290
Stiamo cercando di trovare il numero 19.

76
00:03:22,290 --> 00:03:25,380
Il primo elemento di questo
matrice si trova a indice zero,

77
00:03:25,380 --> 00:03:28,880
e l'ultimo elemento di questa
matrice si trova a 14 dell'indice.

78
00:03:28,880 --> 00:03:31,430
E così chiameremo quelle di inizio e fine.

79
00:03:31,430 --> 00:03:35,387
>> Così si calcola il punto medio per
aggiungendo 0 plus 14 diviso 2;

80
00:03:35,387 --> 00:03:36,720
punto medio abbastanza semplice.

81
00:03:36,720 --> 00:03:40,190
E possiamo dire che
il punto medio è ora 7.

82
00:03:40,190 --> 00:03:43,370
Quindi è 15 quello che stiamo cercando?

83
00:03:43,370 --> 00:03:43,940
No non lo è.

84
00:03:43,940 --> 00:03:45,270
Stiamo cercando 19.

85
00:03:45,270 --> 00:03:49,400
Ma noi sappiamo che il 19 è maggiore
di quello che abbiamo trovato al centro.

86
00:03:49,400 --> 00:03:52,470
>> Che cosa possiamo fare è
modificare il punto iniziale

87
00:03:52,470 --> 00:03:57,280
essere appena a destra della
punto medio, e ripetere il processo.

88
00:03:57,280 --> 00:04:01,690
E quando lo facciamo, ora diciamo la
nuovo punto di partenza è la posizione di matrice 8.

89
00:04:01,690 --> 00:04:07,220
Quello che abbiamo fatto è efficace
ignorato tutto a sinistra di 15.

90
00:04:07,220 --> 00:04:09,570
Abbiamo eliminato la metà
del problema, e ora,

91
00:04:09,570 --> 00:04:13,510
invece di dover cercare
oltre 15 elementi nella nostra gamma,

92
00:04:13,510 --> 00:04:15,610
non ci resta che cercare su 7.

93
00:04:15,610 --> 00:04:17,706
Quindi 8 è il nuovo punto di partenza.

94
00:04:17,706 --> 00:04:19,600
14 è ancora il punto finale.

95
00:04:19,600 --> 00:04:21,430
>> E adesso, andiamo su questo nuovo.

96
00:04:21,430 --> 00:04:22,810
Calcoliamo il nuovo punto medio.

97
00:04:22,810 --> 00:04:27,130
8 plus 14 è 22, diviso 2 è 11.

98
00:04:27,130 --> 00:04:28,660
È questo ciò che stiamo cercando?

99
00:04:28,660 --> 00:04:30,110
No non lo è.

100
00:04:30,110 --> 00:04:32,930
Siamo alla ricerca di un valore che è
meno di quello che abbiamo appena trovato.

101
00:04:32,930 --> 00:04:34,721
Così stiamo andando a ripetere
il processo di nuovo.

102
00:04:34,721 --> 00:04:38,280
Stiamo andando a cambiare il punto finale
essere appena a sinistra del punto medio.

103
00:04:38,280 --> 00:04:41,800
Così il nuovo punto finale diventa 10.

104
00:04:41,800 --> 00:04:44,780
E ora, questa è l'unica parte di
l'array dobbiamo ordinare attraverso.

105
00:04:44,780 --> 00:04:48,460
Così ora abbiamo eliminato
12 dei 15 elementi.

106
00:04:48,460 --> 00:04:51,550
Sappiamo che se 19
esiste nella matrice, esso

107
00:04:51,550 --> 00:04:57,210
deve esistere da qualche parte tra elemento
numero 8 e l'elemento numero 10.

108
00:04:57,210 --> 00:04:59,400
>> Così si calcola di nuovo il nuovo punto medio.

109
00:04:59,400 --> 00:05:02,900
8 più 10 è 18, diviso 2 è 9.

110
00:05:02,900 --> 00:05:05,074
E in questo caso, guarda, la
bersaglio è al centro.

111
00:05:05,074 --> 00:05:06,740
Abbiamo trovato esattamente quello che stiamo cercando.

112
00:05:06,740 --> 00:05:07,780
Possiamo fermarci.

113
00:05:07,780 --> 00:05:10,561
Abbiamo completato con successo
una ricerca binaria.

114
00:05:10,561 --> 00:05:11,060
Tutto ok.

115
00:05:11,060 --> 00:05:13,930
Così sappiamo questo algoritmo
funziona se l'obiettivo è

116
00:05:13,930 --> 00:05:16,070
qualche parte all'interno della matrice.

117
00:05:16,070 --> 00:05:19,060
Fa questo lavoro algoritmo se
il bersaglio non è nell'array?

118
00:05:19,060 --> 00:05:20,810
Bene, cominciamo esso
di nuovo, e questa volta,

119
00:05:20,810 --> 00:05:23,380
diamo un'occhiata per l'elemento
16, che visivamente si vede

120
00:05:23,380 --> 00:05:25,620
non esiste nessuna parte nella matrice.

121
00:05:25,620 --> 00:05:27,110
>> Il punto di partenza è di nuovo 0.

122
00:05:27,110 --> 00:05:28,590
Il punto finale è di nuovo 14.

123
00:05:28,590 --> 00:05:32,490
Questi sono gli indici della prima e
ultimi elementi della matrice completa.

124
00:05:32,490 --> 00:05:36,057
E andremo attraverso il processo che abbiamo appena
ha attraversato di nuovo, cercando di trovare 16,

125
00:05:36,057 --> 00:05:39,140
anche se visivamente, possiamo già
dire che non sarà lì.

126
00:05:39,140 --> 00:05:43,450
Vogliamo solo per assicurarsi che questo algoritmo
sarà, infatti, ancora funzionare in qualche modo

127
00:05:43,450 --> 00:05:46,310
e non appena ci lascia
bloccato in un ciclo infinito.

128
00:05:46,310 --> 00:05:48,190
>> Allora qual è il passo prima?

129
00:05:48,190 --> 00:05:50,230
Calcolare il punto medio
dell'array corrente.

130
00:05:50,230 --> 00:05:52,790
Qual è il punto medio
della matrice corrente?

131
00:05:52,790 --> 00:05:54,410
Beh, è ​​il 7, giusto?

132
00:05:54,410 --> 00:05:57,560
14 più 0 diviso 2 è 7.

133
00:05:57,560 --> 00:05:59,280
È 15 quello che stiamo cercando?

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

135
00:05:59,780 --> 00:06:02,930
E 'abbastanza vicino, ma stiamo cercando
per un valore leggermente più grande di quello.

136
00:06:02,930 --> 00:06:06,310
>> Così sappiamo che sta andando a
in nessun posto a fianco di 15.

137
00:06:06,310 --> 00:06:08,540
L'obiettivo è superiore
cosa c'è nel punto medio.

138
00:06:08,540 --> 00:06:12,450
E così abbiamo impostato il nuovo punto di partenza per
essere appena a destra del centro.

139
00:06:12,450 --> 00:06:16,130
Il punto medio è attualmente 7, così
diciamo che il nuovo punto di partenza è di 8.

140
00:06:16,130 --> 00:06:18,130
E quello che abbiamo in modo efficace
fatto di nuovo viene ignorato

141
00:06:18,130 --> 00:06:21,150
tutta la metà sinistra della matrice.

142
00:06:21,150 --> 00:06:23,750
>> Ora, ripetiamo la
elaborare ancora una volta.

143
00:06:23,750 --> 00:06:24,910
Calcolare il nuovo punto medio.

144
00:06:24,910 --> 00:06:29,350
8 plus 14 è 22, diviso 2 è 11.

145
00:06:29,350 --> 00:06:31,060
È 23 quello che stiamo cercando?

146
00:06:31,060 --> 00:06:31,870
Sfortunatamente no.

147
00:06:31,870 --> 00:06:34,930
Stiamo cercando per un valore
questo è inferiore a 23.

148
00:06:34,930 --> 00:06:37,850
E così in questo caso, stiamo andando
per modificare il punto finale di essere solo

149
00:06:37,850 --> 00:06:40,035
alla sinistra del punto medio corrente.

150
00:06:40,035 --> 00:06:43,440
Il punto medio attuale è 11, e
quindi imposteremo il nuovo punto finale

151
00:06:43,440 --> 00:06:46,980
per la prossima volta che andiamo
attraverso questo processo a 10.

152
00:06:46,980 --> 00:06:48,660
>> Ancora una volta, passiamo attraverso il processo di nuovo.

153
00:06:48,660 --> 00:06:49,640
Calcolare il punto medio.

154
00:06:49,640 --> 00:06:53,100
8 più 10 diviso 2 è 9.

155
00:06:53,100 --> 00:06:54,750
È 19 quello che stiamo cercando?

156
00:06:54,750 --> 00:06:55,500
Sfortunatamente no.

157
00:06:55,500 --> 00:06:58,050
Stiamo ancora cercando
un numero inferiore a quello.

158
00:06:58,050 --> 00:07:02,060
Così cambieremo il punto finale questa volta
essere appena a sinistra del punto medio.

159
00:07:02,060 --> 00:07:05,532
Il punto centrale è attualmente 9,
quindi il punto finale sarà 8.

160
00:07:05,532 --> 00:07:07,920
E ora, stiamo solo cercando
in un singolo array elemento.

161
00:07:07,920 --> 00:07:10,250
>> Qual è il punto centrale di questo array?

162
00:07:10,250 --> 00:07:13,459
Ebbene, inizia alle 8, essa
termina a 8, il punto medio è 8.

163
00:07:13,459 --> 00:07:14,750
E 'questo che stiamo cercando?

164
00:07:14,750 --> 00:07:16,339
Stiamo cercando 17?

165
00:07:16,339 --> 00:07:17,380
No, stiamo cercando 16.

166
00:07:17,380 --> 00:07:20,160
Quindi, se esiste nella matrice,
deve esistere da qualche parte

167
00:07:20,160 --> 00:07:21,935
a sinistra di dove ci troviamo attualmente.

168
00:07:21,935 --> 00:07:23,060
Allora cosa dobbiamo fare?

169
00:07:23,060 --> 00:07:26,610
Beh, imposteremo il punto finale di essere solo
alla sinistra del punto medio corrente.

170
00:07:26,610 --> 00:07:29,055
Così cambieremo il punto finale a 7.

171
00:07:29,055 --> 00:07:32,120
Vedete quello che è appena
è successo qui, però?

172
00:07:32,120 --> 00:07:33,370
Guardate qui ora.

173
00:07:33,370 --> 00:07:35,970
>> Start è ora maggiore di fine.

174
00:07:35,970 --> 00:07:39,620
In effetti, le due estremità
della nostra gamma hanno attraversato,

175
00:07:39,620 --> 00:07:42,252
e il punto di partenza è
ora, dopo il punto finale.

176
00:07:42,252 --> 00:07:43,960
Beh, questo non lo fa
alcun senso, giusto?

177
00:07:43,960 --> 00:07:47,960
Così ora, quello che possiamo dire è che abbiamo
avere una matrice sub di dimensioni 0.

178
00:07:47,960 --> 00:07:50,110
E una volta che siamo arrivati ​​al
questo punto, possiamo ora

179
00:07:50,110 --> 00:07:53,940
garantire che elemento 16
non esiste nella matrice,

180
00:07:53,940 --> 00:07:56,280
perché il punto di partenza
e punto finale hanno attraversato.

181
00:07:56,280 --> 00:07:58,340
E quindi non è lì.

182
00:07:58,340 --> 00:08:01,340
Ora, si noti che questo è un po '
diverso rispetto al punto di inizio e fine

183
00:08:01,340 --> 00:08:02,900
punto è la stessa.

184
00:08:02,900 --> 00:08:05,030
Se fossimo stati alla ricerca
per 17, sarebbe

185
00:08:05,030 --> 00:08:08,870
stato nella matrice, e il punto iniziale
e il punto finale di quella dell'ultima iterazione

186
00:08:08,870 --> 00:08:11,820
prima di quei punti attraversati,
avremmo trovato 17 lì.

187
00:08:11,820 --> 00:08:15,510
E 'solo quando attraversano che possiamo
garantire che l'elemento non fa

188
00:08:15,510 --> 00:08:17,180
esistere nella matrice.

189
00:08:17,180 --> 00:08:20,260
>> Quindi cerchiamo di prendere un sacco meno
passaggi di ricerca lineare.

190
00:08:20,260 --> 00:08:23,250
Nel peggiore dei casi, abbiamo avuto
per dividere una lista di n elementi

191
00:08:23,250 --> 00:08:27,770
ripetutamente a metà per trovare il bersaglio,
sia perché l'elemento di destinazione

192
00:08:27,770 --> 00:08:33,110
sarà da qualche parte negli ultimi
divisione, o non esiste affatto.

193
00:08:33,110 --> 00:08:37,830
Quindi, nel caso peggiore, dobbiamo
dividere i array-- fai a saperlo?

194
00:08:37,830 --> 00:08:40,510
Log di n volte; noi
tagliare il problema

195
00:08:40,510 --> 00:08:42,610
in mezzo un certo numero di volte.

196
00:08:42,610 --> 00:08:45,160
Quel numero di volte che è log n.

197
00:08:45,160 --> 00:08:46,510
>> Qual è la migliore delle ipotesi?

198
00:08:46,510 --> 00:08:48,899
Beh, la prima volta che ci siamo
calcolare il punto medio,

199
00:08:48,899 --> 00:08:50,190
troviamo quello che stiamo cercando.

200
00:08:50,190 --> 00:08:52,150
In tutti i precedenti
esempi su ricerca binaria

201
00:08:52,150 --> 00:08:55,489
abbiamo appena andato oltre, se avessimo
state cercando l'elemento 15,

202
00:08:55,489 --> 00:08:57,030
avremmo trovato subito.

203
00:08:57,030 --> 00:08:58,321
E 'stato proprio all'inizio.

204
00:08:58,321 --> 00:09:01,200
Questo è stato il punto medio di
il primo tentativo di una scissione

205
00:09:01,200 --> 00:09:03,950
di una divisione in ricerca binaria.

206
00:09:03,950 --> 00:09:06,350
>> E così nel peggiore
caso, ricerca binaria corre

207
00:09:06,350 --> 00:09:11,580
in log n, che è sostanzialmente migliore
di ricerca lineare, nel caso peggiore.

208
00:09:11,580 --> 00:09:16,210
Nel migliore dei casi, binario
ricerca viene eseguito in omega di 1.

209
00:09:16,210 --> 00:09:18,990
Così la ricerca binaria è molto
meglio di ricerca lineare,

210
00:09:18,990 --> 00:09:23,270
ma bisogna fare i conti con il processo di
ordinamento la matrice prima di poter

211
00:09:23,270 --> 00:09:26,140
sfruttare la potenza di ricerca binaria.

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

213
00:09:27,130 --> 00:09:29,470
Questo è CS 50.

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