>> ROB BOWDEN: Hola, soy Rob.
¿Cómo nos empleamos una búsqueda binaria?
Vamos a ver.
Por lo tanto, tenga en cuenta que esta búsqueda nos vamos para aplicar de forma recursiva.
Usted podría también poner en práctica la búsqueda binaria iterativa, por lo que si se hizo,
que está perfectamente bien.
>> Ahora primero, recordemos lo que el parámetros de búsqueda están destinados a ser.
Aquí, vemos valor int, que es supone que es el valor que el usuario es
buscando.
Vemos la matriz valores int, que es la matriz en la que estamos
la búsqueda de valor.
Y vemos int n, que es la duración de nuestra matriz.
>> Ahora, primero lo primero.
Verificamos si n es igual a 0, en cuyo caso volvemos falsa.
Eso es sólo decir si tenemos un vacío matriz, el valor no es clara en un
matriz vacía, por lo que puede devolver false.
>> Ahora, en realidad queremos hacer el binario Búsqueda parte de búsqueda binaria.
Por lo tanto, queremos encontrar el medio elemento de esta matriz.
Aquí, decimos media es igual a n dividida por 2, ya que el elemento medio es
va a ser la longitud de nuestra matriz dividida por 2.
Ahora vamos a comprobar para ver si el elemento medio es igual al valor que estamos
buscando.
Así que si los valores de media es igual a valor, puede devolver cierto ya que encontramos el
valor en nuestra matriz.
>> Pero si eso no era cierto, ahora tenemos que hacer el recursiva
paso de búsqueda binaria.
Tenemos que buscar o bien a la izquierdo de la matriz o de la
centro de la matriz.
Así que aquí, decimos si los valores en el medio es menos de su valor, eso significa que el valor
fue mayor que la mitad de la matriz.
Así que el valor debe ser el de la derecha de la elemento que acabamos de ver.
>> Así que aquí, vamos a buscar de forma recursiva.
Y vamos a ver lo que estamos pasando a este en un segundo.
Pero vamos a buscar a la derecha del elemento medio.
Y en el otro caso, lo que significa que valor fue de menos de la mitad de la
matriz, y así vamos para buscar a la izquierda.
Ahora, la izquierda va a ser un poco más fácil de ver.
Así, vemos aquí que estamos recursiva llamando búsqueda donde la primera
argumento es, de nuevo, el valor estamos mirando por encima.
El segundo argumento va a ser el matriz que buscábamos terminado.
Y el último elemento actual es medio.
Recuerde que el último parámetro es nuestra int n, por lo que esa es la duración de nuestra matriz.
>> En la llamada recursiva a buscar, estamos ahora diciendo que la longitud de la
array es medio.
Por lo tanto, si nuestra matriz era de tamaño 20 y buscado en el índice 10, ya que en medio es
20 dividido entre 2, eso significa que estamos pasar 10 como la nueva
longitud de nuestra matriz.
Recuerde que cuando usted tiene una matriz de longitud 10, eso significa que la validez
los elementos están en los índices de 0 a 9.
Así que esto es exactamente lo que queremos especificar nuestra gama actualizada - la izquierda
matriz desde el elemento medio.
>> Así que, mirando hacia la derecha es un poco más difícil.
Ahora en primer lugar, vamos a considerar la longitud de la matriz a la derecha de la
elemento medio.
Por lo tanto, si nuestra matriz era de tamaño n, entonces el nueva matriz será de tamaño n menos
menos la mitad 1.
Por lo tanto, vamos a pensar en n menos medio.
>> Una vez más, si la matriz fueron de tamaño 20 y dividimos por 2 para obtener el medio,
por lo que el medio es 10, entonces n menos medio nos va a dar el 10, así que 10
elementos a la derecha del centro.
Pero también tenemos la menos 1, ya que no queremos
incluir el propio medio.
Entonces n menos media menos 1 nos da la número total de elementos a la derecha
del índice medio de la matriz.
>> Ahora aquí, recordar que el medio parámetro es la matriz de valores.
Así que aquí, estamos pasando un actualizado array valores.
Esto además de los valores, más medio 1 es diciendo realmente recursiva llamada
búsqueda, pasando por una nueva matriz, donde que la nueva matriz comienza en el medio
más uno de nuestra serie los valores originales.
>> Una sintaxis alternativa para que, ahora que que ha comenzado a ver los punteros, es
valores ampersand plus media 1.
Así, toma la dirección del centro además de un elemento de los valores.
>> Ahora, si usted no estaba cómodo modificación de una serie como esa,
También podría haber implementado esta usando una función auxiliar recursiva, donde
función auxiliar que toma más argumentos.
Así que en lugar de tomar sólo el valor, matriz, y el tamaño de la matriz,
la función auxiliar podría tomar más argumentos, incluidos el índice más bajo
que a usted le preocupan en la matriz y el índice superior que se preocupa
sobre la matriz.
>> Y así no perder de vista tanto de la menor índice y el índice superior, que no lo hacen
tenga que modificar nunca la valores originales matriz.
Usted sólo puede seguir utilizar la matriz de valores.
Pero aquí, notamos que no necesitamos un ayudante funcionar, siempre y cuando estemos
dispuestos para modificar el original valores de array.
Estamos dispuestos a pasar un valores actualizados.
>> Ahora, no podemos búsqueda binaria sobre una matriz que es clasificar.
Así que vamos a obtener esta resuelto.
Ahora, observe que tipo es las dos y parámetros int valores, que es el
matriz que estamos ordenar y int n, que es la longitud de la matriz que
estamos ordenación.
Así pues, aquí queremos implementar un algoritmo de ordenación
es decir o de n al cuadrado.
Usted puede optar por la ordenación de burbuja, la selección tipo, o la ordenación por inserción, o
algún otro tipo que no tenemos visto en clase.
Pero aquí, vamos a utilizar la selección de género.
>> Por lo tanto, vamos a repetir sobre toda la matriz.
Bueno, aquí vemos que estamos iterando de 0 a n menos 1.
¿Por qué no todo el camino hasta el n?
Bueno, si ya hemos solucionó la primera N menos 1 elementos, entonces el
último elemento de lo que ya debe ser en el lugar correcto, por lo que la clasificación más
toda la matriz.
>> Ahora, recuerda cómo la selección tipo de obras.
Vamos a repasar toda la matriz buscando el valor mínimo
la matriz y el palo que al principio.
A continuación vamos a repasar toda la array de nuevo en busca de la segunda
elemento más pequeño, y el palo que en la segunda posición en el
matriz, y así sucesivamente.
Entonces, eso es lo que esta haciendo.
>> Aquí, estamos viendo que estamos estableciendo el mínimo actual
valor para el índice i.
Así que en la primera iteración, vamos considerar el valor mínimo para ser
el comienzo de nuestra matriz.
Entonces, vamos a repetir el resto de la gama, verificando
ver si hay algún elemento más pequeño que la que estamos actualmente
teniendo en cuenta el mínimo.
>> Así que aquí, los valores j más uno - que es menos de lo que somos en la actualidad
teniendo en cuenta el mínimo.
Entonces vamos a actualizar lo que creemos que es el mínimo para
índice j más 1.
Por lo tanto, hacer que a través de toda la matriz, y después de este bucle, mínimo
debe ser el elemento mínimo de la posición i-ésima de la matriz.
>> Una vez que tengamos eso, podemos intercambiar la valor mínimo en la posición i-ésima
en la matriz.
Así que esto es sólo un intercambio estándar.
Nosotros guardamos en un valor temporal - el valor i-ésimo de la matriz -
puesto en el valor i-ésimo de la matriz de la valor mínimo que pertenece allí,
y luego almacenar de nuevo en donde el valor mínimo actual que solía ser el
i-ésimo valor de la matriz, por lo que que no nos perdemos.
>> Así, que continúa en la siguiente iteración.
Vamos a empezar a buscar el segundo valor mínimo y que inserte en el
segunda posición.
En la tercera iteración, buscaremos el tercer valor mínimo y el inserto
que en la tercera posición, y así hasta que tenemos una matriz ordenada.
Mi nombre es Rob, y esto era una especie de selección.