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.