1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Ciao, sono Rob.

3
00:00:15,010 --> 00:00:16,790
Come ci avvaliamo di una ricerca binaria?

4
00:00:16,790 --> 00:00:18,770
Andiamo a scoprirlo.

5
00:00:18,770 --> 00:00:23,400
Quindi, si noti che questa ricerca stiamo andando
di attuare in modo ricorsivo.

6
00:00:23,400 --> 00:00:27,470
Si potrebbe anche implementare la ricerca binaria
iterativo, quindi se avete fatto questo,

7
00:00:27,470 --> 00:00:29,280
che è perfettamente bene.

8
00:00:29,280 --> 00:00:32,820
>> Ora in primo luogo, ricordiamo quello che il
parametri di ricerca sono destinati ad essere.

9
00:00:32,820 --> 00:00:36,120
Qui, vediamo il valore int, che è
dovrebbe essere il valore che l'utente è

10
00:00:36,120 --> 00:00:37,320
cercando.

11
00:00:37,320 --> 00:00:40,800
Vediamo la matrice valori int, che
è la matrice in cui siamo

12
00:00:40,800 --> 00:00:42,520
ricerca di valore.

13
00:00:42,520 --> 00:00:45,602
E vediamo int n, che è
la lunghezza del nostro array.

14
00:00:45,602 --> 00:00:47,410
>> Ora, la prima cosa in primo luogo.

15
00:00:47,410 --> 00:00:51,350
Noi controlliamo per vedere se n è uguale a 0, in
qual caso torniamo false.

16
00:00:51,350 --> 00:00:54,770
Questo è solo dicendo che se abbiamo un vuoto
matrice, il valore non è chiaramente in un

17
00:00:54,770 --> 00:00:57,860
matrice vuota, in modo da poter restituire false.

18
00:00:57,860 --> 00:01:01,250
>> Ora, vogliamo davvero fare il binario
la ricerca parte di ricerca binaria.

19
00:01:01,250 --> 00:01:04,780
Quindi, vogliamo trovare al centro
elemento di questa matrice.

20
00:01:04,780 --> 00:01:09,130
Ecco, diciamo mezzo è uguale a n divisa
da 2, poiché l'elemento centrale è

21
00:01:09,130 --> 00:01:12,240
andando essere la lunghezza di
la nostra gamma diviso per 2.

22
00:01:12,240 --> 00:01:15,040
Ora stiamo andando a controllare per vedere se l'
Elemento centrale è uguale al valore siamo

23
00:01:15,040 --> 00:01:16,160
cercando.

24
00:01:16,160 --> 00:01:21,030
Quindi, se i valori medio uguale valore, abbiamo
può restituire true quando abbiamo trovato il

25
00:01:21,030 --> 00:01:22,810
valore nella nostra matrice.

26
00:01:22,810 --> 00:01:26,380
>> Ma se questo non era vero, ora
abbiamo bisogno di fare il ricorsiva

27
00:01:26,380 --> 00:01:27,840
fase di ricerca binaria.

28
00:01:27,840 --> 00:01:30,450
Dobbiamo cercare sia per l'
sinistra della matrice o al

29
00:01:30,450 --> 00:01:32,320
centro della matrice.

30
00:01:32,320 --> 00:01:39,280
Ecco, diciamo che se i valori al centro è
meno di valore, ciò significa che il valore

31
00:01:39,280 --> 00:01:41,350
è superiore al mezzo
della matrice.

32
00:01:41,350 --> 00:01:45,790
Così valore deve essere alla destra del
elemento che abbiamo appena esaminato.

33
00:01:45,790 --> 00:01:48,090
>> Così qui, stiamo andando a
cercare ricorsivamente.

34
00:01:48,090 --> 00:01:50,320
E vedremo che cosa stiamo passando
a questo in un secondo.

35
00:01:50,320 --> 00:01:53,440
Ma stiamo andando a cercare l'
destra dell'elemento centrale.

36
00:01:53,440 --> 00:01:57,710
E nell'altro caso, ciò significa che
valore era inferiore alla metà del

37
00:01:57,710 --> 00:02:00,660
array, e quindi stiamo andando
per cercare a fianco.

38
00:02:00,660 --> 00:02:03,520
Ora, la sinistra sta per essere
un po 'più facile da guardare.

39
00:02:03,520 --> 00:02:07,770
Quindi, vediamo qui che siamo ricorsivamente
chiamando ricerca in cui la prima

40
00:02:07,770 --> 00:02:10,120
argomento è, ancora una volta, il valore
stiamo guardando oltre.

41
00:02:10,120 --> 00:02:14,970
Il secondo argomento sarà l'
array che stavamo cercando sopra.

42
00:02:14,970 --> 00:02:17,090
E l'ultimo elemento è ora centrale.

43
00:02:17,090 --> 00:02:21,650
Ricordate l'ultimo parametro è il nostro int
n, in modo che la lunghezza del nostro array.

44
00:02:21,650 --> 00:02:25,310
>> Nella chiamata ricorsiva per la ricerca, siamo
ora dicendo che la lunghezza del

45
00:02:25,310 --> 00:02:27,230
array è centrale.

46
00:02:27,230 --> 00:02:32,900
Quindi, se la nostra gamma era di dimensioni 20 e
cercato all'indice 10, in quanto mezzo è

47
00:02:32,900 --> 00:02:36,930
20 diviso 2, questo significa che siamo
passando 10 come nuovo

48
00:02:36,930 --> 00:02:38,300
lunghezza del nostro array.

49
00:02:38,300 --> 00:02:41,910
Ricordate che quando si ha una matrice
di lunghezza 10, significa che il valido

50
00:02:41,910 --> 00:02:45,450
elementi sono negli indici da 0 a 9.

51
00:02:45,450 --> 00:02:50,120
Quindi questo è esattamente ciò che vogliamo
specificare la nostra gamma aggiornata - sinistra

52
00:02:50,120 --> 00:02:53,010
matrice dall'elemento centrale.

53
00:02:53,010 --> 00:02:55,710
>> Così, guardando a destra è
un po 'più difficile.

54
00:02:55,710 --> 00:03:00,170
Ora in primo luogo, consideriamo la lunghezza
della matrice a destra della

55
00:03:00,170 --> 00:03:01,240
elemento centrale.

56
00:03:01,240 --> 00:03:08,390
Quindi, se la nostra matrice era di dimensione n, allora la
nuovo array sarà di dimensione n meno

57
00:03:08,390 --> 00:03:10,140
meno centrale 1.

58
00:03:10,140 --> 00:03:12,530
Quindi, pensiamo di n meno di mezzo.

59
00:03:12,530 --> 00:03:18,710
>> Anche in questo caso, se la matrice fosse di dimensioni 20 e
dividiamo per 2 per ottenere la metà,

60
00:03:18,710 --> 00:03:23,540
così il mezzo è 10, allora n meno mezzo
sta per darci 10, quindi 10

61
00:03:23,540 --> 00:03:25,330
elementi a destra del centro.

62
00:03:25,330 --> 00:03:27,780
Ma abbiamo anche questo meno
1, dal momento che non vogliamo

63
00:03:27,780 --> 00:03:29,700
includere mezzo stesso.

64
00:03:29,700 --> 00:03:34,190
Così n meno di mezzo meno 1 ci dà l'
numero totale di elementi a destra

65
00:03:34,190 --> 00:03:36,800
dell'indice medio nella matrice.

66
00:03:36,800 --> 00:03:41,870
>> Ora qui, ricordare che la centrale
parametro è l'array valori.

67
00:03:41,870 --> 00:03:46,180
Così qui, stiamo passando un
I valori aggiornati array.

68
00:03:46,180 --> 00:03:50,930
Questi valori plus plus mezzo 1 è
in realtà dire ricorsivamente chiama

69
00:03:50,930 --> 00:03:56,460
ricerca, passando in un nuovo array, dove
nuova matrice che inizia a metà

70
00:03:56,460 --> 00:03:59,370
più uno dei nostri valori dell'array originale.

71
00:03:59,370 --> 00:04:05,400
>> Una sintassi alternativa per questo, ora che
hai iniziato a vedere i puntatori, è

72
00:04:05,400 --> 00:04:10,170
I valori Ampersand più centrale 1.

73
00:04:10,170 --> 00:04:17,149
Quindi, prendete l'indirizzo del centro
più un elemento di valori.

74
00:04:17,149 --> 00:04:23,690
>> Ora, se tu non fossi comodo
modifica di un array come quello,

75
00:04:23,690 --> 00:04:28,900
potrebbe anche aver implementato questo utilizzando
una funzione di supporto ricorsiva, dove

76
00:04:28,900 --> 00:04:31,680
che la funzione di supporto prende
più argomenti.

77
00:04:31,680 --> 00:04:36,610
Così, invece di prendere solo il valore,
matrice, e la dimensione della matrice,

78
00:04:36,610 --> 00:04:42,315
la funzione di supporto potrebbe richiedere più
argomenti, tra cui l'indice inferiore

79
00:04:42,315 --> 00:04:45,280
che si preoccupano della matrice
e l'indice superiore che si cura

80
00:04:45,280 --> 00:04:46,300
sulla matrice.

81
00:04:46,300 --> 00:04:49,770
>> E quindi mantenere traccia dei valori inferiori
indice e l'indice superiore, non lo fanno

82
00:04:49,770 --> 00:04:52,780
necessario modificare mai l'
valori originali array.

83
00:04:52,780 --> 00:04:56,390
Si può solo continuare a
utilizzare la matrice valori.

84
00:04:56,390 --> 00:04:59,540
Ma qui, notiamo non abbiamo bisogno di un aiuto
funzionare finché siamo

85
00:04:59,540 --> 00:05:01,760
disposti a modificare l'originale
valori array.

86
00:05:01,760 --> 00:05:05,020
Siamo disposti a passare in
un valori aggiornati.

87
00:05:05,020 --> 00:05:09,140
>> Ora, non possiamo ricerca binaria su
una matrice che è indifferenziati.

88
00:05:09,140 --> 00:05:12,220
Quindi, cerchiamo di ottenere questo risolto.

89
00:05:12,220 --> 00:05:17,650
Ora, si noti che tipo è passato due
parametri int valori, che rappresenta l'

90
00:05:17,650 --> 00:05:21,110
matrice che stiamo ordinamento, e int n,
che è la lunghezza della matrice che

91
00:05:21,110 --> 00:05:22,250
stiamo ordinamento.

92
00:05:22,250 --> 00:05:24,840
Così, qui vogliamo implementare
un algoritmo di ordinamento

93
00:05:24,840 --> 00:05:26,690
distante o di n squadrato.

94
00:05:26,690 --> 00:05:30,560
Si può scegliere bubble sort, selezione
ordinamento, o insertion sort, o

95
00:05:30,560 --> 00:05:32,670
qualche altro tipo che non abbiamo
visto in classe.

96
00:05:32,670 --> 00:05:36,380
Ma qui, stiamo andando a
utilizzare selection sort.

97
00:05:36,380 --> 00:05:40,030
>> Quindi, stiamo andando a scorrere
sull'intera matrice.

98
00:05:40,030 --> 00:05:44,360
Bene, qui vediamo che stiamo scorrendo
da 0 a n meno 1.

99
00:05:44,360 --> 00:05:45,990
Perché non tutta la strada fino al n?

100
00:05:45,990 --> 00:05:49,320
Beh, se abbiamo già risolto il primo
n meno 1 elementi, poi il

101
00:05:49,320 --> 00:05:54,420
ultimo elemento di ciò che deve essere già
nel posto giusto, in modo da classificare over

102
00:05:54,420 --> 00:05:56,520
l'intero array.

103
00:05:56,520 --> 00:05:58,770
>> Ora, ricordare come la selezione
ordinamento funziona.

104
00:05:58,770 --> 00:06:01,950
Stiamo per andare oltre l'intero array
cercando il valore minimo in

105
00:06:01,950 --> 00:06:04,480
la matrice e il bastone che
all'inizio.

106
00:06:04,480 --> 00:06:07,610
Poi abbiamo intenzione di andare oltre l'intero
matrice ancora cercando il secondo

107
00:06:07,610 --> 00:06:10,410
più piccolo elemento, e bastone che
nella seconda posizione nella

108
00:06:10,410 --> 00:06:12,100
matrice, e così via.

109
00:06:12,100 --> 00:06:14,330
Quindi, questo è ciò che questo sta facendo.

110
00:06:14,330 --> 00:06:17,290
>> Qui, stiamo vedendo che siamo
impostando la corrente minima

111
00:06:17,290 --> 00:06:20,030
valore per l'indice i-esimo.

112
00:06:20,030 --> 00:06:23,160
Così la prima iterazione, stiamo andando
considerare il valore minimo sia

113
00:06:23,160 --> 00:06:25,030
l'inizio della nostra matrice.

114
00:06:25,030 --> 00:06:28,500
Poi, stiamo andando a scorrere la
resto della matrice, controllando

115
00:06:28,500 --> 00:06:31,870
vedere se ci sono elementi più piccolo
quello che siamo attualmente

116
00:06:31,870 --> 00:06:33,900
considerando il minimo.

117
00:06:33,900 --> 00:06:38,840
>> Quindi, ecco, i valori j più uno - che è
meno di quello che stiamo attualmente

118
00:06:38,840 --> 00:06:40,380
considerando il minimo.

119
00:06:40,380 --> 00:06:42,940
Poi andremo ad aggiornare quello che
pensiamo che è il minimo per

120
00:06:42,940 --> 00:06:44,640
indice j più 1.

121
00:06:44,640 --> 00:06:48,540
Quindi, fare che tutta la matrice,
e dopo questo ciclo for, minimo

122
00:06:48,540 --> 00:06:53,160
dovrebbe essere l'elemento minimo da
la posizione i-esima dell'array.

123
00:06:53,160 --> 00:06:57,350
>> Una volta che abbiamo che, possiamo scambiare il
valore minimo nella posizione i-esima

124
00:06:57,350 --> 00:06:58,230
nella matrice.

125
00:06:58,230 --> 00:07:00,130
Quindi questo è solo uno swap standard.

126
00:07:00,130 --> 00:07:03,940
Noi conserviamo in un valore temporaneo -
il valore i-esimo dell'array -

127
00:07:03,940 --> 00:07:08,460
mettere in valore i-esimo dell'array l'
valore minimo che ci appartiene,

128
00:07:08,460 --> 00:07:13,580
e quindi memorizzare nuovamente dentro cui la
valore minimo di corrente era la

129
00:07:13,580 --> 00:07:16,460
i-esimo valore nella matrice, così
che non abbiamo perdiamo.

130
00:07:16,460 --> 00:07:20,510
>> Quindi, che prosegue sulla
l'iterazione successiva.

131
00:07:20,510 --> 00:07:23,480
Inizieremo cercando il secondo
valore minimo e inserire che nella

132
00:07:23,480 --> 00:07:24,590
seconda posizione.

133
00:07:24,590 --> 00:07:27,440
Nella terza iterazione, cercheremo
il valore minimo e terzo inserto

134
00:07:27,440 --> 00:07:31,550
che nella terza posizione, e così
fino a quando abbiamo un array ordinato.

135
00:07:31,550 --> 00:07:33,820
Il mio nome è Rob, e questo
era selection sort.

136
00:07:33,820 --> 00:07:39,456