>> 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.