[GIOCO MUSICA] 

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 applicando anche sort che ordina l'array chiamato valori. 

Quindi cerchiamo di affrontare la ricerca. Ricerca è implementata come ricerca lineare, ma si può fare molto meglio. Ricerca lineare è implementato in O del tempo n, che è abbastanza lento. Anche se si può verificare qualsiasi elenco attribuitogli. 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ì? 

Beh, diamo un'occhiata a un esempio. Dato un array di valori, pagliaio, stiamo andando a guardare un ago. E in questo esempio, il numero intero tre. 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 zero. 

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, dato che tre, 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. Quindi hai ragione limite può stringere la limiti della ricerca in un pochino di più, e così via e così via fino a trovare l'ago. 

Così che cosa il pseudocodice assomiglia? Beh, mentre ci stiamo ancora guardando attraverso la lista e avere ancora elementi per guardare in, prendiamo la metà della lista, e confrontare tale valore medio 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 solo 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 hai ancora trovato l'ago, poi si return false perché l'ago sicuramente non è nel pagliaio. 

Ora, una cosa semplice di questo pseudocodice in ricerca binaria è che può essere interpretata 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 Naturalmente, ma non sanno che è un opzione se vuoi provare. 

Ora diamo un'occhiata alle liste. Ordina prende un array e il numero intero n, che è la dimensione della matrice. Ora ci sono diversi tipi di sorta, e si può guardare ad un certo pantaloncini per dimostrazioni e spiegazioni. Il tipo di ritorno per la nostra funzione di ordinamento è nullo. Quindi questo significa che non stiamo andando di restituire qualsiasi matrice da ordinamento. Stiamo davvero andando a cambiare molto matrice che è stata approvata in noi. 

E questo è possibile perché gli array sono passati per riferimento in C. Ora faremo vedere di più su questo più tardi, ma il differenza essenziale tra di passaggio in qualcosa come un intero e di passaggio in una matrice, è che quando si passare in un numero intero, C è solo andare a fare una copia di tale numero intero e passare alla funzione. Non verrà modificata la variabile originale una volta che la funzione è terminata. Con una matrice, d'altra parte, è non andare a fare una copia, e sarete effettivamente modificando il molto matrice stessa. 

Così un tipo di ordinamento è il tipo di selezione. L'ordinamento per selezione funziona a partire da l'inizio, e poi si scorre sopra e trovare il più piccolo elemento. E poi si scambiano che più piccolo elemento con il primo. E poi si passa al secondo elemento , Trovare il prossimo più piccolo elemento, e poi scambiare che con la secondo elemento dell'array perché il primo elemento è già ordinato. E così poi si continua per ogni elemento per identificare il più piccolo valore e scambiando fuori. 

Per I è uguale a 0, il primo elemento per n meno 1, si sta andando a confrontare ogni valore prossimo dopo che e trovare l'indice del valore minimo. Una volta trovato l'indice di valore minimo, si può scambiare quel valore di matrice minimo e la matrice I. 

Un altro tipo di genere che si può attuare è bubble sort. Così bubble sort itera l'elenco confrontando elementi adiacenti e scambiando gli elementi che sono nell'ordine sbagliato. E questo modo, l'elemento più grande sarà bolla fino alla fine. E la lista è ordinata una volta non è più elementi sono stati scambiati. 

Quindi questi sono due esempi di specie algoritmi che si possono attuare per il programma find. Una volta terminata ordinamento, e hai fatta di ricerca, sei finito. Il mio nome è Zamyla, e questo è CS50. 

[GIOCO MUSICA]