>> ROB BOWDEN: Ola, eu son Rob.
Como é que imos empregar unha procura binaria?
Imos descubrir.
Así, teña en conta que esta investigación imos para aplicar de forma recursiva.
Tamén pode aplicar busca binaria iterativa, polo que, se fixo iso,
iso é perfectamente ben.
>> Agora, en primeiro lugar, imos lembrar que a parámetros descriptor están destinadas a ser.
Aquí vemos o valor int, que é debería ser o valor que o usuario é
procurar.
Vemos a matriz valores int, que é a matriz en que estamos
busca de valor.
E vemos int n, que é a extensión de a matriz.
>> Agora, o primeiro en primeiro lugar.
Nós encontramos a ver se n é igual a 0, en caso en que voltar false.
Isto é só dicir se temos un baleiro matriz, o valor non está claramente nunha
array baleiro, para que poidamos voltar false.
>> Agora, nós realmente queremos facer a binario investigación parte busca binaria.
Entón, nós queremos atopar o medio elemento deste array.
Aquí, nós dicimos que é igual a medio n dividido por 2, xa que o elemento do medio é
será a lonxitude de nosa disposición dividido por 2.
Agora imos comprobar a ver se o elemento do medio é igual ao valor que estamos
procurar.
Así, se os valores de media igual valor, pode devolver certo sempre que atopamos o
valor na nosa matriz.
>> Pero se iso non era certo, agora o que necesitamos facer o recursiva
etapa de procura binaria.
Necesitamos buscar tanto para o esquerda da matriz ou para o
medio da matriz.
Entón, aquí, nós dicimos que os valores no medio é menos que o valor, isto significa que o valor de
era maior que o medio da matriz.
Así, o valor debe ser á dereita do elemento que só mirou.
>> Entón, aquí, nós imos buscar de forma recursiva.
E nós imos ollar para o que está pasando para iso nun segundo.
Pero nós imos buscar a dereito de o elemento do medio.
E, no outro caso, iso significa que valor foi menor que a metade do
array, e así imos para buscar á esquerda.
Agora, a esquerda será un pouco máis fácil de ollar.
Así, podemos ver aquí que estamos de recursivamente chamando de investigación onde o primeiro
argumento é, de novo, o valor de nós estamos mirando por riba.
O segundo argumento será o matriz que estabamos buscando.
E o último elemento é agora medio.
Teña en conta que o último parámetro é o noso int n, de xeito que é a lonxitude da nosa matriz.
>> Na chamada recursiva para investigar, estamos agora dicir que o longo do
matriz é medio.
Así, se o noso abano era de tamaño 20 e que investigados no índice 10, xa é medio
20 dividido por 2, o que significa que estamos pasando 10 como o novo
lonxitude da nosa matriz.
Lembre que cando ten unha matriz de lonxitude 10, isto significa que o válido
elementos están en índices de 0 a 9.
Entón, iso é o que queremos especificar a nosa gama actualizados - á esquerda
matriz desde o elemento central.
>> Entón, mirando para a dereita é un pouco máis difícil.
Agora en primeiro lugar, imos considerar a lonxitude da matriz á dereita do
elemento do medio.
Así, se o noso panel foi de tamaño n, entón o nova matriz será de tamaño n menos
medio menos 1.
Entón, imos pensar en n menos medio.
>> Unha vez máis, a matriz eran de tamaño 20 e dividimos por 2 para obter o medio,
de xeito que o medio é de 10, a continuación, n menos de media vai dar 10, entón 10
elementos á dereita do medio.
Pero nós tamén temos este menos 1, xa que non quere
inclúen o propio medio.
Entón n menos medio menos 1 dános a número total de elementos á dereita
do índice medio na matriz.
>> Agora, aquí, lembre que o medio parámetro é a matriz de valores.
Entón, aquí, estamos pasando un variedade valores actualizados.
Estes valores Plus Plus medio 1 é realmente dicir de forma recursiva chamar
investigación, pasando nunha nova matriz, onde que nova matriz comeza no medio
unha das nosas matriz orixinal valores.
>> Unha sintaxe alternativa para iso, agora que se comezou a ver os punteiros, é
valores ampersand máis medio 1.
Entón, tome a dirección do medio ademais dun elemento de valores.
>> Agora, se non fose cómodo modificar unha matriz así,
tamén podería ter implantado esta usando unha función auxiliar recursiva, onde
que ten función auxiliar máis argumentos.
Entón, en vez de tomar só o valor, matriz, e o tamaño da matriz,
a función auxiliar pode levar máis argumentos, ata o máis pequeno índice
que lle importaría con na matriz eo índice superior que lle importa
sobre a matriz.
>> E así, manter o control de ambos os máis baixos índice eo índice superior, non
precisan sempre modificar o variedade valores orixinais.
Pode só seguir utilizar a matriz de valores.
Pero aquí, entender que non necesitamos un axudante funciona, sempre que somos
dispostos para modificar o orixinal variedade valores.
Estamos dispostos a pasar en un valores actualizados.
>> Agora non podemos procura binaria sobre unha matriz que é indiferenciado.
Entón, imos resolver iso.
Agora, teña en conta que tipo é pasado dous parámetros int valores, que é o
matriz que estamos clasificación e int n, que é a lonxitude da matriz que
estamos clasificación.
Entón, aquí queremos implantar un algoritmo de ordenación
que é o cadrado de n.
Pode escoller bubble sort, selección sort, ou ordenación por inserción, ou
algún outro tipo que non ten visto en clase.
Pero aquí, imos usar a selección tipo.
>> Entón, nós imos facer unha iteración ao longo de toda a matriz.
Ben, aquí vemos que estamos interactuar de 0 a n menos 1.
Por que non todo o camiño ata o n?
Ben, se xa clasificadas na primeira N menos un elementos, entón o
último elemento que xa debe estar no lugar correcto, para que a clasificación máis
toda a matriz.
>> Agora, lembre-se como a selección tipo funciona.
Nós imos pasar por riba de toda a matriz buscar o valor mínimo en
a matriz e vara que no inicio.
Entón imos pasar por riba de toda a disposición de novo mirando para a segunda
menor elemento, e pau que na segunda posición
matriz, e así por diante.
Entón, iso é o que este fai.
>> Aquí, nós estamos a ver que estamos definindo o mínimo actual
valor para o índice i-th.
Entón, na primeira iteración, imos considerar o valor mínimo para ser
o inicio da nosa matriz.
Entón, nós imos facer unha iteración sobre o resto da matriz, a verificación de
ver se hai calquera elemento menor que o que estamos actualmente
considerando o mínimo.
>> Entón, aquí, os valores j máis un - que é menos que o que somos na actualidade
considerando o mínimo.
Entón, imos actualizar o que pensamos que é o mínimo para
índice j + 1.
Entón, faino en toda a matriz, e tras este loop for, mínimo
debe ser o mínimo do elemento a posición i-th na matriz.
>> Así que temos iso, podemos cambiar o valor mínimo para a posición i-th
na matriz.
Polo tanto, esta é só un intercambio de defecto.
Nós gardados nun valor temporal - o valor i-th na matriz -
poñer no valor i-th na matriz do valor mínimo que pertence hai,
e logo, almacenar volta a onde a valor mínimo actual adoitaba ser o
i-th valor na matriz, de xeito que non perde-lo.
>> Así, que continúa en a seguinte iteración.
Nós imos comezar a ollar para a segunda valor mínimo e introducir tanto no
segunda posición.
Na terceira iteración, imos ollar para o valor mínimo e terceiro inserido
que na terceira posición, e así por ata temos un array ordenado.
O meu nome é Rob, e este era a selección tipo.