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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Oi, eu sou Rob.

3
00:00:15,010 --> 00:00:16,790
Como é que vamos empregar uma busca binária?

4
00:00:16,790 --> 00:00:18,770
Vamos descobrir.

5
00:00:18,770 --> 00:00:23,400
Assim, note que esta pesquisa vamos
para implementar de forma recursiva.

6
00:00:23,400 --> 00:00:27,470
Você também pode implementar busca binária
iterativa, por isso, se você fez isso,

7
00:00:27,470 --> 00:00:29,280
isso é perfeitamente bem.

8
00:00:29,280 --> 00:00:32,820
>> Agora, primeiro, vamos lembrar o que a
parâmetros para pesquisa são destinadas a ser.

9
00:00:32,820 --> 00:00:36,120
Aqui, vemos o valor int, que é
deveria ser o valor que o usuário é

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

11
00:00:37,320 --> 00:00:40,800
Vemos a matriz valores int, que
é a matriz em 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 extensão de a matriz.

14
00:00:45,602 --> 00:00:47,410
>> Agora, a primeira coisa em primeiro lugar.

15
00:00:47,410 --> 00:00:51,350
Nós verificamos para ver se n é igual a 0, em
caso em que retornar false.

16
00:00:51,350 --> 00:00:54,770
Isso é apenas dizer se temos um vazio
matriz, o valor não está claramente em uma

17
00:00:54,770 --> 00:00:57,860
array vazio, para que possamos retornar false.

18
00:00:57,860 --> 00:01:01,250
>> Agora, nós realmente queremos fazer o binário
pesquisa parte de busca binária.

19
00:01:01,250 --> 00:01:04,780
Então, nós queremos encontrar o meio
elemento desse array.

20
00:01:04,780 --> 00:01:09,130
Aqui, nós dizemos que é igual a meio n dividido
por 2, uma vez que o elemento do meio é

21
00:01:09,130 --> 00:01:12,240
vai ser o comprimento de
nossa disposição dividido por 2.

22
00:01:12,240 --> 00:01:15,040
Agora vamos verificar para ver se o
elemento do meio é igual ao valor que estamos

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

24
00:01:16,160 --> 00:01:21,030
Assim, se os valores de média igual valor,
pode retornar verdadeiro desde que encontramos o

25
00:01:21,030 --> 00:01:22,810
valor em nossa matriz.

26
00:01:22,810 --> 00:01:26,380
>> Mas se isso não era verdade, agora
o que precisamos fazer o recursiva

27
00:01:26,380 --> 00:01:27,840
etapa de busca binária.

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

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

30
00:01:32,320 --> 00:01:39,280
Então, aqui, nós dizemos que os valores no meio é
menos do que o valor, isso significa que o valor de

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

32
00:01:41,350 --> 00:01:45,790
Assim, o valor deve ser para a direita do
elemento que apenas olhou para.

33
00:01:45,790 --> 00:01:48,090
>> Então, aqui, nós vamos
pesquisar de forma recursiva.

34
00:01:48,090 --> 00:01:50,320
E nós vamos olhar para o que está passando
para isso em um segundo.

35
00:01:50,320 --> 00:01:53,440
Mas nós vamos procurar para o
direito de o elemento do meio.

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

37
00:01:57,710 --> 00:02:00,660
array, e assim vamos
para pesquisar para a esquerda.

38
00:02:00,660 --> 00:02:03,520
Agora, a esquerda vai ser
um pouco mais fácil de se olhar.

39
00:02:03,520 --> 00:02:07,770
Assim, vemos aqui que estamos de forma recursiva
chamando de pesquisa onde o primeiro

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

41
00:02:10,120 --> 00:02:14,970
O segundo argumento vai ser o
matriz que estávamos à procura de.

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

43
00:02:17,090 --> 00:02:21,650
Lembre-se o último parâmetro é a nossa int
n, de modo que é o comprimento da nossa matriz.

44
00:02:21,650 --> 00:02:25,310
>> Na chamada recursiva para pesquisar, estamos
agora dizer que o comprimento do

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

46
00:02:27,230 --> 00:02:32,900
Assim, se o nosso leque era de tamanho 20 e que
pesquisados ​​no índice 10, já é meio

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

48
00:02:36,930 --> 00:02:38,300
comprimento da nossa matriz.

49
00:02:38,300 --> 00:02:41,910
Lembre-se que quando você tem uma matriz
de comprimento 10, isso significa que o válido

50
00:02:41,910 --> 00:02:45,450
elementos estão em índices de 0 a 9.

51
00:02:45,450 --> 00:02:50,120
Então, isso é exatamente o que queremos
especificar a nossa gama atualizados - à esquerda

52
00:02:50,120 --> 00:02:53,010
matriz a partir do elemento central.

53
00:02:53,010 --> 00:02:55,710
>> Então, olhando para a direita é
um pouco mais difícil.

54
00:02:55,710 --> 00:03:00,170
Agora em primeiro lugar, vamos considerar o comprimento
da matriz para a direita do

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

56
00:03:01,240 --> 00:03:08,390
Assim, se o nosso painel foi de tamanho n, então o
nova matriz será de tamanho n menos

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

58
00:03:10,140 --> 00:03:12,530
Então, vamos pensar em n menos meio.

59
00:03:12,530 --> 00:03:18,710
>> Mais uma vez, se a matriz eram de tamanho 20 e
dividimos por 2 para obter o meio,

60
00:03:18,710 --> 00:03:23,540
de modo que o meio é de 10, em seguida, n menos de meia
vai nos dar 10, então 10

61
00:03:23,540 --> 00:03:25,330
elementos à direita do meio.

62
00:03:25,330 --> 00:03:27,780
Mas nós também temos este menos
1, uma vez que não quer

63
00:03:27,780 --> 00:03:29,700
incluem o próprio meio.

64
00:03:29,700 --> 00:03:34,190
Então n menos meio menos 1 nos dá a
número total de elementos à direita

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

66
00:03:36,800 --> 00:03:41,870
>> Agora, aqui, lembre-se que o meio
parâmetro é a matriz de valores.

67
00:03:41,870 --> 00:03:46,180
Então, aqui, nós estamos passando um
variedade valores atualizados.

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

69
00:03:50,930 --> 00:03:56,460
pesquisa, passando em uma nova matriz, onde
que nova matriz começa no meio

70
00:03:56,460 --> 00:03:59,370
mais uma de nossas matriz original valores.

71
00:03:59,370 --> 00:04:05,400
>> Uma sintaxe alternativa para isso, agora que
você começou a ver os ponteiros, é

72
00:04:05,400 --> 00:04:10,170
valores ampersand mais meio 1.

73
00:04:10,170 --> 00:04:17,149
Então, pegue o endereço do meio
além de um elemento de valores.

74
00:04:17,149 --> 00:04:23,690
>> Agora, se você não fosse confortável
modificar uma matriz assim, você

75
00:04:23,690 --> 00:04:28,900
também poderia ter implementado esta usando
uma função auxiliar recursiva, onde

76
00:04:28,900 --> 00:04:31,680
que tem função auxiliar
mais argumentos.

77
00:04:31,680 --> 00:04:36,610
Então, em vez de tomar apenas o valor,
matriz, e o tamanho da matriz,

78
00:04:36,610 --> 00:04:42,315
a função auxiliar pode demorar mais
argumentos, inclusive o menor índice

79
00:04:42,315 --> 00:04:45,280
que você se importaria com na matriz
eo índice superior que você se importa

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

81
00:04:46,300 --> 00:04:49,770
>> E assim, manter o controle de ambos os mais baixos
índice eo índice superior, você não

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

83
00:04:52,780 --> 00:04:56,390
Você pode apenas continuar a
usar a matriz de valores.

84
00:04:56,390 --> 00:04:59,540
Mas aqui, perceber que não precisamos de um ajudante
funcionar, desde que nós somos

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

86
00:05:01,760 --> 00:05:05,020
Estamos dispostos a passar em
um valores atualizados.

87
00:05:05,020 --> 00:05:09,140
>> Agora, não podemos busca binária sobre
uma matriz que é indiferenciado.

88
00:05:09,140 --> 00:05:12,220
Então, vamos resolver isso.

89
00:05:12,220 --> 00:05:17,650
Agora, observe que tipo é passado dois
parâmetros int valores, que é o

90
00:05:17,650 --> 00:05:21,110
matriz que estamos classificação e int n,
que é o comprimento da matriz que

91
00:05:21,110 --> 00:05:22,250
estamos classificação.

92
00:05:22,250 --> 00:05:24,840
Então, aqui queremos implementar
um algoritmo de ordenação

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

94
00:05:26,690 --> 00:05:30,560
Você pode escolher bubble sort, seleção
sort, ou ordenação por inserção, ou

95
00:05:30,560 --> 00:05:32,670
algum outro tipo que não tem
visto em sala de aula.

96
00:05:32,670 --> 00:05:36,380
Mas aqui, vamos
usar a seleção tipo.

97
00:05:36,380 --> 00:05:40,030
>> Então, nós vamos fazer uma iteração
ao longo de toda a matriz.

98
00:05:40,030 --> 00:05:44,360
Bem, aqui nós vemos que estamos interagindo
de 0 a n menos 1.

99
00:05:44,360 --> 00:05:45,990
Por que não todo o caminho até ao n?

100
00:05:45,990 --> 00:05:49,320
Bem, se nós já classificadas na primeira
N menos um elementos, então o

101
00:05:49,320 --> 00:05:54,420
último elemento que já deve estar
no lugar correto, para que a classificação mais

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 seleção
tipo funciona.

104
00:05:58,770 --> 00:06:01,950
Nós vamos passar por cima de toda a matriz
procurar o valor mínimo em

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

106
00:06:04,480 --> 00:06:07,610
Então vamos passar por cima de toda a
disposição novamente olhando para a segunda

107
00:06:07,610 --> 00:06:10,410
menor elemento, e pau que
na segunda posição

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

109
00:06:12,100 --> 00:06:14,330
Então, isso é o que este está fazendo.

110
00:06:14,330 --> 00:06:17,290
>> Aqui, nós estamos vendo que estamos
definindo o mínimo atual

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ão, na primeira iteração, vamos
considerar o valor mínimo para ser

113
00:06:23,160 --> 00:06:25,030
o início da nossa matriz.

114
00:06:25,030 --> 00:06:28,500
Então, nós vamos fazer uma iteração sobre o
restante da matriz, a verificação de

115
00:06:28,500 --> 00:06:31,870
ver se há qualquer elemento menor do que
o que estamos atualmente

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

117
00:06:33,900 --> 00:06:38,840
>> Então, aqui, os valores j mais um - que é
menos do que o que somos atualmente

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

119
00:06:40,380 --> 00:06:42,940
Então, vamos atualizar o que
nós 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ão, faça isso em toda a matriz,
e após este loop for, mínimo

122
00:06:48,540 --> 00:06:53,160
deve ser o mínimo do elemento
a posição i-th na matriz.

123
00:06:53,160 --> 00:06:57,350
>> Assim que tivermos isso, podemos trocar o
valor mínimo para a posição i-th

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

125
00:06:58,230 --> 00:07:00,130
Portanto, esta é apenas uma troca de padrão.

126
00:07:00,130 --> 00:07:03,940
Nós armazenamos em um valor temporário -
o valor i-th na matriz -

127
00:07:03,940 --> 00:07:08,460
colocar no valor i-th na matriz do
valor mínimo que pertence há,

128
00:07:08,460 --> 00:07:13,580
e, em seguida, armazenar volta para onde o
valor mínimo atual costumava ser o

129
00:07:13,580 --> 00:07:16,460
i-th valor na matriz, de modo
que não perdê-lo.

130
00:07:16,460 --> 00:07:20,510
>> Assim, que continua em
a próxima iteração.

131
00:07:20,510 --> 00:07:23,480
Nós vamos começar a olhar para a segunda
valor mínimo e inserir isso no

132
00:07:23,480 --> 00:07:24,590
segunda posição.

133
00:07:24,590 --> 00:07:27,440
Na terceira iteração, vamos olhar para
o valor mínimo e terceiro inserto

134
00:07:27,440 --> 00:07:31,550
que na terceira posição, e assim por
até temos um array ordenado.

135
00:07:31,550 --> 00:07:33,820
Meu nome é Rob, e este
era a seleção tipo.

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