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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Hola, soy Rob.

3
00:00:15,010 --> 00:00:16,790
¿Cómo nos empleamos una búsqueda binaria?

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

5
00:00:18,770 --> 00:00:23,400
Por lo tanto, tenga en cuenta que esta búsqueda nos vamos
para aplicar de forma recursiva.

6
00:00:23,400 --> 00:00:27,470
Usted podría también poner en práctica la búsqueda binaria
iterativa, por lo que si se hizo,

7
00:00:27,470 --> 00:00:29,280
que está perfectamente bien.

8
00:00:29,280 --> 00:00:32,820
>> Ahora primero, recordemos lo que el
parámetros de búsqueda están destinados a ser.

9
00:00:32,820 --> 00:00:36,120
Aquí, vemos valor int, que es
supone que es el valor que el usuario es

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

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

12
00:00:40,800 --> 00:00:42,520
la búsqueda de valor.

13
00:00:42,520 --> 00:00:45,602
Y vemos int n, que es
la duración de nuestra matriz.

14
00:00:45,602 --> 00:00:47,410
>> Ahora, primero lo primero.

15
00:00:47,410 --> 00:00:51,350
Verificamos si n es igual a 0, en
cuyo caso volvemos falsa.

16
00:00:51,350 --> 00:00:54,770
Eso es sólo decir si tenemos un vacío
matriz, el valor no es clara en un

17
00:00:54,770 --> 00:00:57,860
matriz vacía, por lo que puede devolver false.

18
00:00:57,860 --> 00:01:01,250
>> Ahora, en realidad queremos hacer el binario
Búsqueda parte de búsqueda binaria.

19
00:01:01,250 --> 00:01:04,780
Por lo tanto, queremos encontrar el medio
elemento de esta matriz.

20
00:01:04,780 --> 00:01:09,130
Aquí, decimos media es igual a n dividida
por 2, ya que el elemento medio es

21
00:01:09,130 --> 00:01:12,240
va a ser la longitud de
nuestra matriz dividida por 2.

22
00:01:12,240 --> 00:01:15,040
Ahora vamos a comprobar para ver si el
elemento medio es igual al valor que estamos

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

24
00:01:16,160 --> 00:01:21,030
Así que si los valores de media es igual a valor,
puede devolver cierto ya que encontramos el

25
00:01:21,030 --> 00:01:22,810
valor en nuestra matriz.

26
00:01:22,810 --> 00:01:26,380
>> Pero si eso no era cierto, ahora
tenemos que hacer el recursiva

27
00:01:26,380 --> 00:01:27,840
paso de búsqueda binaria.

28
00:01:27,840 --> 00:01:30,450
Tenemos que buscar o bien a la
izquierdo de la matriz o de la

29
00:01:30,450 --> 00:01:32,320
centro de la matriz.

30
00:01:32,320 --> 00:01:39,280
Así que aquí, decimos si los valores en el medio es
menos de su valor, eso significa que el valor

31
00:01:39,280 --> 00:01:41,350
fue mayor que la mitad
de la matriz.

32
00:01:41,350 --> 00:01:45,790
Así que el valor debe ser el de la derecha de la
elemento que acabamos de ver.

33
00:01:45,790 --> 00:01:48,090
>> Así que aquí, vamos a
buscar de forma recursiva.

34
00:01:48,090 --> 00:01:50,320
Y vamos a ver lo que estamos pasando
a este en un segundo.

35
00:01:50,320 --> 00:01:53,440
Pero vamos a buscar a la
derecha del elemento medio.

36
00:01:53,440 --> 00:01:57,710
Y en el otro caso, lo que significa que
valor fue de menos de la mitad de la

37
00:01:57,710 --> 00:02:00,660
matriz, y así vamos
para buscar a la izquierda.

38
00:02:00,660 --> 00:02:03,520
Ahora, la izquierda va a ser
un poco más fácil de ver.

39
00:02:03,520 --> 00:02:07,770
Así, vemos aquí que estamos recursiva
llamando búsqueda donde la primera

40
00:02:07,770 --> 00:02:10,120
argumento es, de nuevo, el valor
estamos mirando por encima.

41
00:02:10,120 --> 00:02:14,970
El segundo argumento va a ser el
matriz que buscábamos terminado.

42
00:02:14,970 --> 00:02:17,090
Y el último elemento actual es medio.

43
00:02:17,090 --> 00:02:21,650
Recuerde que el último parámetro es nuestra int
n, por lo que esa es la duración de nuestra matriz.

44
00:02:21,650 --> 00:02:25,310
>> En la llamada recursiva a buscar, estamos
ahora diciendo que la longitud de la

45
00:02:25,310 --> 00:02:27,230
array es medio.

46
00:02:27,230 --> 00:02:32,900
Por lo tanto, si nuestra matriz era de tamaño 20 y
buscado en el índice 10, ya que en medio es

47
00:02:32,900 --> 00:02:36,930
20 dividido entre 2, eso significa que estamos
pasar 10 como la nueva

48
00:02:36,930 --> 00:02:38,300
longitud de nuestra matriz.

49
00:02:38,300 --> 00:02:41,910
Recuerde que cuando usted tiene una matriz
de longitud 10, eso significa que la validez

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

51
00:02:45,450 --> 00:02:50,120
Así que esto es exactamente lo que queremos
especificar nuestra gama actualizada - la izquierda

52
00:02:50,120 --> 00:02:53,010
matriz desde el elemento medio.

53
00:02:53,010 --> 00:02:55,710
>> Así que, mirando hacia la derecha es
un poco más difícil.

54
00:02:55,710 --> 00:03:00,170
Ahora en primer lugar, vamos a considerar la longitud
de la matriz a la derecha de la

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

56
00:03:01,240 --> 00:03:08,390
Por lo tanto, si nuestra matriz era de tamaño n, entonces el
nueva matriz será de tamaño n menos

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

58
00:03:10,140 --> 00:03:12,530
Por lo tanto, vamos a pensar en n menos medio.

59
00:03:12,530 --> 00:03:18,710
>> Una vez más, si la matriz fueron de tamaño 20 y
dividimos por 2 para obtener el medio,

60
00:03:18,710 --> 00:03:23,540
por lo que el medio es 10, entonces n menos medio
nos va a dar el 10, así que 10

61
00:03:23,540 --> 00:03:25,330
elementos a la derecha del centro.

62
00:03:25,330 --> 00:03:27,780
Pero también tenemos la menos
1, ya que no queremos

63
00:03:27,780 --> 00:03:29,700
incluir el propio medio.

64
00:03:29,700 --> 00:03:34,190
Entonces n menos media menos 1 nos da la
número total de elementos a la derecha

65
00:03:34,190 --> 00:03:36,800
del índice medio de la matriz.

66
00:03:36,800 --> 00:03:41,870
>> Ahora aquí, recordar que el medio
parámetro es la matriz de valores.

67
00:03:41,870 --> 00:03:46,180
Así que aquí, estamos pasando un
actualizado array valores.

68
00:03:46,180 --> 00:03:50,930
Esto además de los valores, más medio 1 es
diciendo realmente recursiva llamada

69
00:03:50,930 --> 00:03:56,460
búsqueda, pasando por una nueva matriz, donde
que la nueva matriz comienza en el medio

70
00:03:56,460 --> 00:03:59,370
más uno de nuestra serie los valores originales.

71
00:03:59,370 --> 00:04:05,400
>> Una sintaxis alternativa para que, ahora que
que ha comenzado a ver los punteros, es

72
00:04:05,400 --> 00:04:10,170
valores ampersand plus media 1.

73
00:04:10,170 --> 00:04:17,149
Así, toma la dirección del centro
además de un elemento de los valores.

74
00:04:17,149 --> 00:04:23,690
>> Ahora, si usted no estaba cómodo
modificación de una serie como esa,

75
00:04:23,690 --> 00:04:28,900
También podría haber implementado esta usando
una función auxiliar recursiva, donde

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

77
00:04:31,680 --> 00:04:36,610
Así que en lugar de tomar sólo el valor,
matriz, y el tamaño de la matriz,

78
00:04:36,610 --> 00:04:42,315
la función auxiliar podría tomar más
argumentos, incluidos el índice más bajo

79
00:04:42,315 --> 00:04:45,280
que a usted le preocupan en la matriz
y el índice superior que se preocupa

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

81
00:04:46,300 --> 00:04:49,770
>> Y así no perder de vista tanto de la menor
índice y el índice superior, que no lo hacen

82
00:04:49,770 --> 00:04:52,780
tenga que modificar nunca la
valores originales matriz.

83
00:04:52,780 --> 00:04:56,390
Usted sólo puede seguir
utilizar la matriz de valores.

84
00:04:56,390 --> 00:04:59,540
Pero aquí, notamos que no necesitamos un ayudante
funcionar, siempre y cuando estemos

85
00:04:59,540 --> 00:05:01,760
dispuestos para modificar el original
valores de array.

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

87
00:05:05,020 --> 00:05:09,140
>> Ahora, no podemos búsqueda binaria sobre
una matriz que es clasificar.

88
00:05:09,140 --> 00:05:12,220
Así que vamos a obtener esta resuelto.

89
00:05:12,220 --> 00:05:17,650
Ahora, observe que tipo es las dos y
parámetros int valores, que es el

90
00:05:17,650 --> 00:05:21,110
matriz que estamos ordenar y int n,
que es la longitud de la matriz que

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

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

93
00:05:24,840 --> 00:05:26,690
es decir o de n al cuadrado.

94
00:05:26,690 --> 00:05:30,560
Usted puede optar por la ordenación de burbuja, la selección
tipo, o la ordenación por inserción, o

95
00:05:30,560 --> 00:05:32,670
algún otro tipo que no tenemos
visto en clase.

96
00:05:32,670 --> 00:05:36,380
Pero aquí, vamos a
utilizar la selección de género.

97
00:05:36,380 --> 00:05:40,030
>> Por lo tanto, vamos a repetir
sobre toda la matriz.

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

99
00:05:44,360 --> 00:05:45,990
¿Por qué no todo el camino hasta el n?

100
00:05:45,990 --> 00:05:49,320
Bueno, si ya hemos solucionó la primera
N menos 1 elementos, entonces el

101
00:05:49,320 --> 00:05:54,420
último elemento de lo que ya debe ser
en el lugar correcto, por lo que la clasificación más

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

103
00:05:56,520 --> 00:05:58,770
>> Ahora, recuerda cómo la selección
tipo de obras.

104
00:05:58,770 --> 00:06:01,950
Vamos a repasar toda la matriz
buscando el valor mínimo

105
00:06:01,950 --> 00:06:04,480
la matriz y el palo que
al principio.

106
00:06:04,480 --> 00:06:07,610
A continuación vamos a repasar toda la
array de nuevo en busca de la segunda

107
00:06:07,610 --> 00:06:10,410
elemento más pequeño, y el palo que
en la segunda posición en el

108
00:06:10,410 --> 00:06:12,100
matriz, y así sucesivamente.

109
00:06:12,100 --> 00:06:14,330
Entonces, eso es lo que esta haciendo.

110
00:06:14,330 --> 00:06:17,290
>> Aquí, estamos viendo que estamos
estableciendo el mínimo actual

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

112
00:06:20,030 --> 00:06:23,160
Así que en la primera iteración, vamos
considerar el valor mínimo para ser

113
00:06:23,160 --> 00:06:25,030
el comienzo de nuestra matriz.

114
00:06:25,030 --> 00:06:28,500
Entonces, vamos a repetir el
resto de la gama, verificando

115
00:06:28,500 --> 00:06:31,870
ver si hay algún elemento más pequeño que
la que estamos actualmente

116
00:06:31,870 --> 00:06:33,900
teniendo en cuenta el mínimo.

117
00:06:33,900 --> 00:06:38,840
>> Así que aquí, los valores j más uno - que es
menos de lo que somos en la actualidad

118
00:06:38,840 --> 00:06:40,380
teniendo en cuenta el mínimo.

119
00:06:40,380 --> 00:06:42,940
Entonces vamos a actualizar lo
que creemos que es el mínimo para

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

121
00:06:44,640 --> 00:06:48,540
Por lo tanto, hacer que a través de toda la matriz,
y después de este bucle, mínimo

122
00:06:48,540 --> 00:06:53,160
debe ser el elemento mínimo de
la posición i-ésima de la matriz.

123
00:06:53,160 --> 00:06:57,350
>> Una vez que tengamos eso, podemos intercambiar la
valor mínimo en la posición i-ésima

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

125
00:06:58,230 --> 00:07:00,130
Así que esto es sólo un intercambio estándar.

126
00:07:00,130 --> 00:07:03,940
Nosotros guardamos en un valor temporal -
el valor i-ésimo de la matriz -

127
00:07:03,940 --> 00:07:08,460
puesto en el valor i-ésimo de la matriz de la
valor mínimo que pertenece allí,

128
00:07:08,460 --> 00:07:13,580
y luego almacenar de nuevo en donde el
valor mínimo actual que solía ser el

129
00:07:13,580 --> 00:07:16,460
i-ésimo valor de la matriz, por lo que
que no nos perdemos.

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

131
00:07:20,510 --> 00:07:23,480
Vamos a empezar a buscar el segundo
valor mínimo y que inserte en el

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

133
00:07:24,590 --> 00:07:27,440
En la tercera iteración, buscaremos
el tercer valor mínimo y el inserto

134
00:07:27,440 --> 00:07:31,550
que en la tercera posición, y así
hasta que tenemos una matriz ordenada.

135
00:07:31,550 --> 00:07:33,820
Mi nombre es Rob, y esto
era una especie de selección.

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