>> [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]