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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Ola, eu son Rob.

3
00:00:15,010 --> 00:00:16,790
Como é que imos empregar unha procura binaria?

4
00:00:16,790 --> 00:00:18,770
Imos descubrir.

5
00:00:18,770 --> 00:00:23,400
Así, teña en conta que esta investigación imos
para aplicar de forma recursiva.

6
00:00:23,400 --> 00:00:27,470
Tamén pode aplicar busca binaria
iterativa, polo que, se fixo iso,

7
00:00:27,470 --> 00:00:29,280
iso é perfectamente ben.

8
00:00:29,280 --> 00:00:32,820
>> Agora, en primeiro lugar, imos lembrar que a
parámetros descriptor están destinadas a ser.

9
00:00:32,820 --> 00:00:36,120
Aquí vemos o valor int, que é
debería ser o valor que o usuario é

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

11
00:00:37,320 --> 00:00:40,800
Vemos a matriz valores int, que
é a matriz en que estamos

12
00:00:40,800 --> 00:00:42,520
busca de valor.

13
00:00:42,520 --> 00:00:45,602
E vemos int n, que é
a extensión de a matriz.

14
00:00:45,602 --> 00:00:47,410
>> Agora, o primeiro en primeiro lugar.

15
00:00:47,410 --> 00:00:51,350
Nós encontramos a ver se n é igual a 0, en
caso en que voltar false.

16
00:00:51,350 --> 00:00:54,770
Isto é só dicir se temos un baleiro
matriz, o valor non está claramente nunha

17
00:00:54,770 --> 00:00:57,860
array baleiro, para que poidamos voltar false.

18
00:00:57,860 --> 00:01:01,250
>> Agora, nós realmente queremos facer a binario
investigación parte busca binaria.

19
00:01:01,250 --> 00:01:04,780
Entón, nós queremos atopar o medio
elemento deste array.

20
00:01:04,780 --> 00:01:09,130
Aquí, nós dicimos que é igual a medio n dividido
por 2, xa que o elemento do medio é

21
00:01:09,130 --> 00:01:12,240
será a lonxitude de
nosa disposición dividido por 2.

22
00:01:12,240 --> 00:01:15,040
Agora imos comprobar a ver se o
elemento do medio é igual ao valor que estamos

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

24
00:01:16,160 --> 00:01:21,030
Así, se os valores de media igual valor,
pode devolver certo sempre que atopamos o

25
00:01:21,030 --> 00:01:22,810
valor na nosa matriz.

26
00:01:22,810 --> 00:01:26,380
>> Pero se iso non era certo, agora
o que necesitamos facer o recursiva

27
00:01:26,380 --> 00:01:27,840
etapa de procura binaria.

28
00:01:27,840 --> 00:01:30,450
Necesitamos buscar tanto para o
esquerda da matriz ou para o

29
00:01:30,450 --> 00:01:32,320
medio da matriz.

30
00:01:32,320 --> 00:01:39,280
Entón, aquí, nós dicimos que os valores no medio é
menos que o valor, isto significa que o valor de

31
00:01:39,280 --> 00:01:41,350
era maior que o medio
da matriz.

32
00:01:41,350 --> 00:01:45,790
Así, o valor debe ser á dereita do
elemento que só mirou.

33
00:01:45,790 --> 00:01:48,090
>> Entón, aquí, nós imos
buscar de forma recursiva.

34
00:01:48,090 --> 00:01:50,320
E nós imos ollar para o que está pasando
para iso nun segundo.

35
00:01:50,320 --> 00:01:53,440
Pero nós imos buscar a
dereito de o elemento do medio.

36
00:01:53,440 --> 00:01:57,710
E, no outro caso, iso significa que
valor foi menor que a metade do

37
00:01:57,710 --> 00:02:00,660
array, e así imos
para buscar á esquerda.

38
00:02:00,660 --> 00:02:03,520
Agora, a esquerda será
un pouco máis fácil de ollar.

39
00:02:03,520 --> 00:02:07,770
Así, podemos ver aquí que estamos de recursivamente
chamando de investigación onde o primeiro

40
00:02:07,770 --> 00:02:10,120
argumento é, de novo, o valor de
nós estamos mirando por riba.

41
00:02:10,120 --> 00:02:14,970
O segundo argumento será o
matriz que estabamos buscando.

42
00:02:14,970 --> 00:02:17,090
E o último elemento é agora medio.

43
00:02:17,090 --> 00:02:21,650
Teña en conta que o último parámetro é o noso int
n, de xeito que é a lonxitude da nosa matriz.

44
00:02:21,650 --> 00:02:25,310
>> Na chamada recursiva para investigar, estamos
agora dicir que o longo do

45
00:02:25,310 --> 00:02:27,230
matriz é medio.

46
00:02:27,230 --> 00:02:32,900
Así, se o noso abano era de tamaño 20 e que
investigados no índice 10, xa é medio

47
00:02:32,900 --> 00:02:36,930
20 dividido por 2, o que significa que estamos
pasando 10 como o novo

48
00:02:36,930 --> 00:02:38,300
lonxitude da nosa matriz.

49
00:02:38,300 --> 00:02:41,910
Lembre que cando ten unha matriz
de lonxitude 10, isto significa que o válido

50
00:02:41,910 --> 00:02:45,450
elementos están en índices de 0 a 9.

51
00:02:45,450 --> 00:02:50,120
Entón, iso é o que queremos
especificar a nosa gama actualizados - á esquerda

52
00:02:50,120 --> 00:02:53,010
matriz desde o elemento central.

53
00:02:53,010 --> 00:02:55,710
>> Entón, mirando para a dereita é
un pouco máis difícil.

54
00:02:55,710 --> 00:03:00,170
Agora en primeiro lugar, imos considerar a lonxitude
da matriz á dereita do

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

56
00:03:01,240 --> 00:03:08,390
Así, se o noso panel foi de tamaño n, entón o
nova matriz será de tamaño n menos

57
00:03:08,390 --> 00:03:10,140
medio menos 1.

58
00:03:10,140 --> 00:03:12,530
Entón, imos pensar en n menos medio.

59
00:03:12,530 --> 00:03:18,710
>> Unha vez máis, a matriz eran de tamaño 20 e
dividimos por 2 para obter o medio,

60
00:03:18,710 --> 00:03:23,540
de xeito que o medio é de 10, a continuación, n menos de media
vai dar 10, entón 10

61
00:03:23,540 --> 00:03:25,330
elementos á dereita do medio.

62
00:03:25,330 --> 00:03:27,780
Pero nós tamén temos este menos
1, xa que non quere

63
00:03:27,780 --> 00:03:29,700
inclúen o propio medio.

64
00:03:29,700 --> 00:03:34,190
Entón n menos medio menos 1 dános a
número total de elementos á dereita

65
00:03:34,190 --> 00:03:36,800
do índice medio na matriz.

66
00:03:36,800 --> 00:03:41,870
>> Agora, aquí, lembre que o medio
parámetro é a matriz de valores.

67
00:03:41,870 --> 00:03:46,180
Entón, aquí, estamos pasando un
variedade valores actualizados.

68
00:03:46,180 --> 00:03:50,930
Estes valores Plus Plus medio 1 é
realmente dicir de forma recursiva chamar

69
00:03:50,930 --> 00:03:56,460
investigación, pasando nunha nova matriz, onde
que nova matriz comeza no medio

70
00:03:56,460 --> 00:03:59,370
unha das nosas matriz orixinal valores.

71
00:03:59,370 --> 00:04:05,400
>> Unha sintaxe alternativa para iso, agora que
se comezou a ver os punteiros, é

72
00:04:05,400 --> 00:04:10,170
valores ampersand máis medio 1.

73
00:04:10,170 --> 00:04:17,149
Entón, tome a dirección do medio
ademais dun elemento de valores.

74
00:04:17,149 --> 00:04:23,690
>> Agora, se non fose cómodo
modificar unha matriz así,

75
00:04:23,690 --> 00:04:28,900
tamén podería ter implantado esta usando
unha función auxiliar recursiva, onde

76
00:04:28,900 --> 00:04:31,680
que ten función auxiliar
máis argumentos.

77
00:04:31,680 --> 00:04:36,610
Entón, en vez de tomar só o valor,
matriz, e o tamaño da matriz,

78
00:04:36,610 --> 00:04:42,315
a función auxiliar pode levar máis
argumentos, ata o máis pequeno índice

79
00:04:42,315 --> 00:04:45,280
que lle importaría con na matriz
eo índice superior que lle importa

80
00:04:45,280 --> 00:04:46,300
sobre a matriz.

81
00:04:46,300 --> 00:04:49,770
>> E así, manter o control de ambos os máis baixos
índice eo índice superior, non

82
00:04:49,770 --> 00:04:52,780
precisan sempre modificar o
variedade valores orixinais.

83
00:04:52,780 --> 00:04:56,390
Pode só seguir
utilizar a matriz de valores.

84
00:04:56,390 --> 00:04:59,540
Pero aquí, entender que non necesitamos un axudante
funciona, sempre que somos

85
00:04:59,540 --> 00:05:01,760
dispostos para modificar o orixinal
variedade valores.

86
00:05:01,760 --> 00:05:05,020
Estamos dispostos a pasar en
un valores actualizados.

87
00:05:05,020 --> 00:05:09,140
>> Agora non podemos procura binaria sobre
unha matriz que é indiferenciado.

88
00:05:09,140 --> 00:05:12,220
Entón, imos resolver iso.

89
00:05:12,220 --> 00:05:17,650
Agora, teña en conta que tipo é pasado dous
parámetros int valores, que é o

90
00:05:17,650 --> 00:05:21,110
matriz que estamos clasificación e int n,
que é a lonxitude da matriz que

91
00:05:21,110 --> 00:05:22,250
estamos clasificación.

92
00:05:22,250 --> 00:05:24,840
Entón, aquí queremos implantar
un algoritmo de ordenación

93
00:05:24,840 --> 00:05:26,690
que é o cadrado de n.

94
00:05:26,690 --> 00:05:30,560
Pode escoller bubble sort, selección
sort, ou ordenación por inserción, ou

95
00:05:30,560 --> 00:05:32,670
algún outro tipo que non ten
visto en clase.

96
00:05:32,670 --> 00:05:36,380
Pero aquí, imos
usar a selección tipo.

97
00:05:36,380 --> 00:05:40,030
>> Entón, nós imos facer unha iteración
ao longo de toda a matriz.

98
00:05:40,030 --> 00:05:44,360
Ben, aquí vemos que estamos interactuar
de 0 a n menos 1.

99
00:05:44,360 --> 00:05:45,990
Por que non todo o camiño ata o n?

100
00:05:45,990 --> 00:05:49,320
Ben, se xa clasificadas na primeira
N menos un elementos, entón o

101
00:05:49,320 --> 00:05:54,420
último elemento que xa debe estar
no lugar correcto, para que a clasificación máis

102
00:05:54,420 --> 00:05:56,520
toda a matriz.

103
00:05:56,520 --> 00:05:58,770
>> Agora, lembre-se como a selección
tipo funciona.

104
00:05:58,770 --> 00:06:01,950
Nós imos pasar por riba de toda a matriz
buscar o valor mínimo en

105
00:06:01,950 --> 00:06:04,480
a matriz e vara que
no inicio.

106
00:06:04,480 --> 00:06:07,610
Entón imos pasar por riba de toda a
disposición de novo mirando para a segunda

107
00:06:07,610 --> 00:06:10,410
menor elemento, e pau que
na segunda posición

108
00:06:10,410 --> 00:06:12,100
matriz, e así por diante.

109
00:06:12,100 --> 00:06:14,330
Entón, iso é o que este fai.

110
00:06:14,330 --> 00:06:17,290
>> Aquí, nós estamos a ver que estamos
definindo o mínimo actual

111
00:06:17,290 --> 00:06:20,030
valor para o índice i-th.

112
00:06:20,030 --> 00:06:23,160
Entón, na primeira iteración, imos
considerar o valor mínimo para ser

113
00:06:23,160 --> 00:06:25,030
o inicio da nosa matriz.

114
00:06:25,030 --> 00:06:28,500
Entón, nós imos facer unha iteración sobre o
resto da matriz, a verificación de

115
00:06:28,500 --> 00:06:31,870
ver se hai calquera elemento menor que
o que estamos actualmente

116
00:06:31,870 --> 00:06:33,900
considerando o mínimo.

117
00:06:33,900 --> 00:06:38,840
>> Entón, aquí, os valores j máis un - que é
menos que o que somos na actualidade

118
00:06:38,840 --> 00:06:40,380
considerando o mínimo.

119
00:06:40,380 --> 00:06:42,940
Entón, imos actualizar o que
pensamos que é o mínimo para

120
00:06:42,940 --> 00:06:44,640
índice j + 1.

121
00:06:44,640 --> 00:06:48,540
Entón, faino en toda a matriz,
e tras este loop for, mínimo

122
00:06:48,540 --> 00:06:53,160
debe ser o mínimo do elemento
a posición i-th na matriz.

123
00:06:53,160 --> 00:06:57,350
>> Así que temos iso, podemos cambiar o
valor mínimo para a posición i-th

124
00:06:57,350 --> 00:06:58,230
na matriz.

125
00:06:58,230 --> 00:07:00,130
Polo tanto, esta é só un intercambio de defecto.

126
00:07:00,130 --> 00:07:03,940
Nós gardados nun valor temporal -
o valor i-th na matriz -

127
00:07:03,940 --> 00:07:08,460
poñer no valor i-th na matriz do
valor mínimo que pertence hai,

128
00:07:08,460 --> 00:07:13,580
e logo, almacenar volta a onde a
valor mínimo actual adoitaba ser o

129
00:07:13,580 --> 00:07:16,460
i-th valor na matriz, de xeito
que non perde-lo.

130
00:07:16,460 --> 00:07:20,510
>> Así, que continúa en
a seguinte iteración.

131
00:07:20,510 --> 00:07:23,480
Nós imos comezar a ollar para a segunda
valor mínimo e introducir tanto no

132
00:07:23,480 --> 00:07:24,590
segunda posición.

133
00:07:24,590 --> 00:07:27,440
Na terceira iteración, imos ollar para
o valor mínimo e terceiro inserido

134
00:07:27,440 --> 00:07:31,550
que na terceira posición, e así por
ata temos un array ordenado.

135
00:07:31,550 --> 00:07:33,820
O meu nome é Rob, e este
era a selección tipo.

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