ZAMYLA CHAN: La prima cosa che si potrebbe avviso sul ritrovamento è che abbiamo già hanno il codice scritto per noi. Questo è chiamato codice di distribuzione. Quindi non stiamo solo scrivendo il nostro codice da zero più. Piuttosto, stiamo riempiendo i vuoti in qualche codice preesistente. 

Il programma find.c richiede numeri per riempire il pagliaio, cerca l' mucchio di fieno per un ago inseriti dall'utente, e lo fa chiamando ordinamento e ricerca, funzioni definite in helpers.c. Così find.c è scritto già. Il vostro compito è quello di scrivere aiutanti. 

Allora, cosa stiamo facendo? Stiamo implementando due funzioni. Ricerca, che restituisce true se un valore si trova nel pagliaio, di ritorno false se il valore è non nel pagliaio. E poi stiamo attuazione anche sort, che ordina l'array chiamato valori. Quindi cerchiamo di affrontare la ricerca. 

Ricerca è attualmente implementato come una ricerca lineare. Ma si può fare molto meglio di così. Ricerca lineare è implementato in O di n tempo, che è piuttosto lento, sebbene Puoi cercare qualsiasi lista data ad essa. Il vostro compito è quello di implementare la ricerca binaria, che ha tempo di esecuzione O di log n. Questo è abbastanza veloce. 

Ma c'è una clausola. La ricerca binaria può cercare solo attraverso liste pre-ordinati. Perché è così? Bene, diamo un'occhiata a un esempio. Dato un array di valori, pagliaio, stiamo andando a guardare un ago, e in questo , il numero intero 3. 

Il modo in cui ricerca binaria funziona è che confrontiamo il valore medio di la matrice all'ago, molto simile a come abbiamo aperto una rubrica a metà la pagina in settimana 0. Così, dopo aver confrontato il valore medio di l'ago, si può scartare sia l' sinistra oa destra della matrice stringendo i vostri limiti. In questo caso, poiché 3, la nostra ago, è inferiore a 10, il valore medio, la proprio limite può diminuire. 

Ma cercare di rendere i vostri limiti il più stretto possibile. Se il valore medio non è l'ago, poi si sa che non c'è bisogno di includere nella ricerca. Così il vostro limite destro può stringere la limiti della ricerca in un pochino di più, e così via e così via, fino a trovare l'ago. 

Quindi cosa fa il pseudo codice assomiglia? Ebbene, mentre stiamo ancora guardando attraverso l'elenco e ancora elementi da cercare in, prendiamo la metà della lista e confrontare tale valore centrale per il nostro ago. Se sono uguali, allora significa che abbiamo trovato l'ago, e possiamo return true. 

Altrimenti, se l'ago è inferiore il valore medio, allora questo significa che può scartare la metà destra e giusto verificare il lato sinistro della matrice. In caso contrario, ci cerchiamo l' lato destro della matrice. E alla fine, se non si dispone di alcun più elementi lasciati a cercare, ma voi non hanno ancora trovato l'ago, poi si torna falso. Poiché l'ago sicuramente non è nel pagliaio. 

Ora, una cosa semplice di questa pseudo codice binario di ricerca è che può essere interpretato sia come iterativo o implementazione ricorsiva. Quindi sarebbe ricorsiva se si chiama la funzione di ricerca all'interno della ricerca funzionamento su entrambi metà dell'array. Parleremo ricorsione un po ' più avanti nel corso. Ma non sanno che si tratta di un'opzione se vuoi provare.