>> ZAMYLA CHAN: A primeira coisa que você pode aviso sobre descoberta é que já
ter o código escrito para nós.
Isto é chamado código de distribuição.
Portanto, não estamos apenas escrevendo o nosso próprio código do zero mais.
Em vez disso, estamos preenchendo os vazios em algum código pré-existente.
>> O programa find.c solicita números para preencher o palheiro, busca o
monte de feno para uma agulha usuário enviou, e ele faz isso chamando classificar e
busca, funções definidas em helpers.c.
Assim find.c é escrita já.
O seu trabalho é escrever ajudantes.
>> Então, o que estamos fazendo?
Estamos implementando duas funções.
Pesquisa, que retorna true se um valor é encontrado em palheiro, retornando
false se o valor é não no palheiro.
E então nós também estamos implementando espécie, que classifica o array chamado valores.
Então, vamos enfrentar pesquisa.
>> Pesquisa é implementado atualmente como uma busca linear.
Mas você pode fazer muito melhor do que isso.
Busca linear é implementada em O de n tempo, o que é bastante lento, embora
pode procurar qualquer lista que lhe é dado.
Seu trabalho é a implementação de busca binária, que tem tempo de execução O de log n.
Isso é muito rápido.
>> Mas há uma condição.
Pesquisa binária só pode procurar através de listas pré-ordenadas.
Por que isso?
Bem, vamos dar uma olhada em um exemplo.
Dada uma matriz de valores, o palheiro, vamos estar a olhar
por uma agulha, e neste exemplo, o número inteiro 3.
>> A maneira que busca binária funciona é que compararmos o valor médio de
a matriz para a agulha, bem como a forma como abrimos um livro de telefone para o meio
página na Semana 0.
Então, depois de comparar o valor médio para a agulha, você pode descartar ou a
esquerda ou da metade direita da matriz apertando os seus limites.
Neste caso, uma vez que 3, a agulha, é inferior a 10, o valor médio, o
certo limite pode diminuir.
>> Mas tente fazer seus limites tão apertada quanto possível.
Se o valor do meio não é a agulha, então você sabe que você não precisa
incluí-lo em sua busca.
Portanto, o seu limite direito pode apertar a limites da pesquisa apenas um pouquinho mais,
e assim por diante e assim por diante, até que você encontrar sua agulha.
>> Então, o que faz o pseudo código se parece?
Bem, enquanto nós ainda estamos olhando através a lista e ainda ter
elementos para olhar em, tomamos o meio da lista e comparar isso
valor médio para o nosso agulha.
Se eles são iguais, então isso significa que nós temos encontrou a agulha, e podemos
return true.
>> Caso contrário, se a agulha for inferior a o valor médio, em seguida, isso significa que
pode descartar a metade direita e apenas pesquisar o lado esquerdo da matriz.
Caso contrário, nós vamos procurar o lado direito da matriz.
E, no final, se você não tem qualquer mais elementos da esquerda para a busca, mas você
não encontrou sua agulha ainda, então você retornar false.
Porque a agulha definitivamente Não é em palheiro.
>> Agora, uma coisa interessante sobre este pseudo código em busca binária é que ele pode
ser interpretado como um iterativo ou implementação recursiva.
Portanto, seria recursiva se chamado a função de pesquisa dentro da pesquisa
funcionar em qualquer uma das metades da matriz.
Nós vamos cobrir recursão um pouco mais tarde no curso.
Mas sei que ele é uma opção se você gostaria de tentar.