ROB BOWDEN: Oi, eu sou Rob. Como é que vamos empregar uma busca binária? Vamos descobrir. Assim, note que esta pesquisa vamos para implementar de forma recursiva. Você também pode implementar busca binária iterativa, por isso, se você fez isso, isso é perfeitamente bem. 

Agora, primeiro, vamos lembrar o que a parâmetros para pesquisa são destinadas a ser. Aqui, vemos o valor int, que é deveria ser o valor que o usuário é procurando. Vemos a matriz valores int, que é a matriz em que estamos busca de valor. E vemos int n, que é a extensão de a matriz. 

Agora, a primeira coisa em primeiro lugar. Nós verificamos para ver se n é igual a 0, em caso em que retornar false. Isso é apenas dizer se temos um vazio matriz, o valor não está claramente em uma array vazio, para que possamos retornar false. 

Agora, nós realmente queremos fazer o binário pesquisa parte de busca binária. Então, nós queremos encontrar o meio elemento desse array. Aqui, nós dizemos que é igual a meio n dividido por 2, uma vez que o elemento do meio é vai ser o comprimento de nossa disposição dividido por 2. Agora vamos verificar para ver se o elemento do meio é igual ao valor que estamos procurando. Assim, se os valores de média igual valor, pode retornar verdadeiro desde que encontramos o valor em nossa matriz. 

Mas se isso não era verdade, agora o que precisamos fazer o recursiva etapa de busca binária. Precisamos pesquisar tanto para o esquerda da matriz ou para o meio da matriz. Então, aqui, nós dizemos que os valores no meio é menos do que o valor, isso significa que o valor de era maior do que o meio da matriz. Assim, o valor deve ser para a direita do elemento que apenas olhou para. 

Então, aqui, nós vamos pesquisar de forma recursiva. E nós vamos olhar para o que está passando para isso em um segundo. Mas nós vamos procurar para o direito de o elemento do meio. E, no outro caso, isso significa que valor foi menor que a metade do array, e assim vamos para pesquisar para a esquerda. Agora, a esquerda vai ser um pouco mais fácil de se olhar. Assim, vemos aqui que estamos de forma recursiva chamando de pesquisa onde o primeiro argumento é, de novo, o valor de nós estamos olhando por cima. O segundo argumento vai ser o matriz que estávamos à procura de. E o último elemento agora é meio. Lembre-se o último parâmetro é a nossa int n, de modo que é o comprimento da nossa matriz. 

Na chamada recursiva para pesquisar, estamos agora dizer que o comprimento do matriz é meio. Assim, se o nosso leque era de tamanho 20 e que pesquisados ​​no índice 10, já é meio 20 dividido por 2, o que significa que estamos passando 10 como o novo comprimento da nossa matriz. Lembre-se que quando você tem uma matriz de comprimento 10, isso significa que o válido elementos estão em índices de 0 a 9. Então, isso é exatamente o que queremos especificar a nossa gama atualizados - à esquerda matriz a partir do elemento central. 

Então, olhando para a direita é um pouco mais difícil. Agora em primeiro lugar, vamos considerar o comprimento da matriz para a direita do elemento do meio. Assim, se o nosso painel foi de tamanho n, então o nova matriz será de tamanho n menos meio menos 1. Então, vamos pensar em n menos meio. 

Mais uma vez, se a matriz eram de tamanho 20 e dividimos por 2 para obter o meio, de modo que o meio é de 10, em seguida, n menos de meia vai nos dar 10, então 10 elementos à direita do meio. Mas nós também temos este menos 1, uma vez que não quer incluem o próprio meio. Então n menos meio menos 1 nos dá a número total de elementos à direita do índice médio na matriz. 

Agora, aqui, lembre-se que o meio parâmetro é a matriz de valores. Então, aqui, nós estamos passando um variedade valores atualizados. Estes valores Plus Plus meio 1 é realmente dizer de forma recursiva chamar pesquisa, passando em uma nova matriz, onde que nova matriz começa no meio mais uma de nossas matriz original valores. 

Uma sintaxe alternativa para isso, agora que você começou a ver os ponteiros, é valores ampersand mais meio 1. Então, pegue o endereço do meio além de um elemento de valores. 

Agora, se você não fosse confortável modificar uma matriz assim, você também poderia ter implementado esta usando uma função auxiliar recursiva, onde que tem função auxiliar mais argumentos. Então, em vez de tomar apenas o valor, matriz, e o tamanho da matriz, a função auxiliar pode demorar mais argumentos, inclusive o menor índice que você se importaria com na matriz eo índice superior que você se importa sobre a matriz. 

E assim, manter o controle de ambos os mais baixos índice eo índice superior, você não precisam sempre modificar o variedade valores originais. Você pode apenas continuar a usar a matriz de valores. Mas aqui, perceber que não precisamos de um ajudante funcionar, desde que nós somos dispostos para modificar o original variedade valores. Estamos dispostos a passar em um valores atualizados. 

Agora, não podemos busca binária sobre uma matriz que é indiferenciado. Então, vamos resolver isso. Agora, observe que tipo é passado dois parâmetros int valores, que é o matriz que estamos classificação e int n, que é o comprimento da matriz que estamos classificação. Então, aqui queremos implementar um algoritmo de ordenação que é o quadrado de n. Você pode escolher bubble sort, seleção sort, ou ordenação por inserção, ou algum outro tipo que não tem visto em sala de aula. Mas aqui, vamos usar a seleção tipo. 

Então, nós vamos fazer uma iteração ao longo de toda a matriz. Bem, aqui nós vemos que estamos interagindo de 0 a n menos 1. Por que não todo o caminho até ao n? Bem, se nós já classificadas na primeira N menos um elementos, então o último elemento que já deve estar no lugar correto, para que a classificação mais toda a matriz. 

Agora, lembre-se como a seleção tipo funciona. Nós vamos passar por cima de toda a matriz procurar o valor mínimo em a matriz e vara que no início. Então vamos passar por cima de toda a disposição novamente olhando para a segunda menor elemento, e pau que na segunda posição matriz, e assim por diante. Então, isso é o que este está fazendo. 

Aqui, nós estamos vendo que estamos definindo o mínimo atual valor para o índice i-th. Então, na primeira iteração, vamos considerar o valor mínimo para ser o início da nossa matriz. Então, nós vamos fazer uma iteração sobre o restante da matriz, a verificação de ver se há qualquer elemento menor do que o que estamos atualmente considerando o mínimo. 

Então, aqui, os valores j mais um - que é menos do que o que somos atualmente considerando o mínimo. Então, vamos atualizar o que nós pensamos que é o mínimo para índice j + 1. Então, faça isso em toda a matriz, e após este loop for, mínimo deve ser o mínimo do elemento a posição i-th na matriz. 

Assim que tivermos isso, podemos trocar o valor mínimo para a posição i-th na matriz. Portanto, esta é apenas uma troca de padrão. Nós armazenamos em um valor temporário - o valor i-th na matriz - colocar no valor i-th na matriz do valor mínimo que pertence há, e, em seguida, armazenar volta para onde o valor mínimo atual costumava ser o i-th valor na matriz, de modo que não perdê-lo. 

Assim, que continua em a próxima iteração. Nós vamos começar a olhar para a segunda valor mínimo e inserir isso no segunda posição. Na terceira iteração, vamos olhar para o valor mínimo e terceiro inserto que na terceira posição, e assim por até temos um array ordenado. Meu nome é Rob, e este era a seleção tipo.