ZAMYLA CHAN: A primeira cousa que pode aviso sobre descubrimento é que xa ter o código escrito para nós. Isto chámase código de distribución. Polo tanto, non estamos só escribindo o noso propio código de cero máis. Pola contra, estamos cubrindo os baleiros nalgún código pre-existente. 

O programa find.c solicita números para cubrir o palheiro, busca o chea de feno para unha agulla usuario enviou, e el fai iso chamando clasificar e busca, funcións definidas en helpers.c. Así find.c está escrita xa. O seu traballo é escribir axudantes. 

Entón, o que estamos facendo? Estamos aplicando dúas funcións. Investigación, que retorna true se un valor se atopa en palheiro, retornando false se o valor é non no palheiro. E entón nós tamén estamos aplicando especie, que clasifica o array chamado valores. Entón, imos afrontar investigación. 

Busca é aplicado actualmente como unha busca linear. Pero pode facer moito mellor do que iso. Busca linear é aplicada en O de n tempo, o que é moi lento, aínda que pode buscar calquera lista que lle é dado. O seu traballo é a implementación de busca binaria, que ten tempo de execución O de rexistro n. Isto é moi rápido. 

Pero hai unha condición. Busca binaria só pode buscar mediante listas pre-ordenada. Por que isto? Ben, imos dar un ollo a un exemplo. Dada unha matriz de valores, o palheiro, imos estar a ollar por unha agulla, e neste exemplo, o número enteiro 3. 

O xeito que busca binaria funciona é que compararmos o valor medio de a matriz para a agulla, así como o xeito no que abrimos un libro de teléfono para o medio páxina na Semana 0. Entón, despois de comparar o valor medio para a agulla, pode descartar ou a esquerda ou da metade dereita da matriz axustado os seus límites. Neste caso, xa que 3, a agulla, é inferior a 10, o valor medio, o certo límite pode diminuír. 

Pero probe facer os seus límites tan axustado como sexa posible. O valor do medio non é a agulla, entón vostede sabe que non é preciso inclui-lo na súa procura. Polo tanto, o seu límite dereito pode usar a límites da investigación só un pouquiño máis, e así por diante e así por diante, ata que atopa a súa agulla. 

Entón, o que fai o pseudo código se parece? Así, mentres que nós aínda estamos mirando a través a lista e aínda ter elementos para ollar, tomamos o medio da lista e comparar isto valor medio para o noso agulla. Se son iguais, entón iso significa que temos atopou a agulla, e podemos return true. 

En caso contrario, se a agulla é inferior a o valor medio, a continuación, isto significa que pode descartar a metade dereita e só buscar o lado esquerdo da matriz. En caso contrario, nós imos buscar o lado dereito da matriz. E, ao final, se non ten ningún máis elementos de esquerda a procura, pero non atopou a súa agulla aínda, entón voltar false. Porque a agulla definitivamente Non é en palheiro. 

Agora, unha cousa interesante sobre este pseudo código en busca binaria é que pode pode interpretar como un iterativo ou implantación recursiva. Polo tanto, sería recursiva se chama a función de investigación dentro da investigación funciona en calquera das metades da matriz. Nós imos cubrir recursão algo máis tarde no curso. Pero sei que é unha opción Se desexa probar.