>> [RIPRODUZIONE DI BRANI MUSICALI]
DOUG LLOYD: Lineare di ricerca è un algoritmo di noi
possono utilizzare per trovare un elemento in un array.
Un richiamo algoritmo è un insieme passo-passo
di istruzioni per il completamento di un compito.
>> La ricerca lineare algoritmo funziona come segue.
Scorrere attraverso la matrice da sinistra a a destra, alla ricerca di un elemento specificato.
>> In pseudocodice, che è un altro versione distillata di questa frase,
se il primo elemento è quello che stai cercando, ci si può fermare.
In caso contrario, passare all'elemento successivo e andare avanti più e più volte fino a trovare
l'elemento, o non fare.
Così possiamo usare il lineare algoritmo di ricerca, ad esempio,
per trovare il valore bersaglio nove in questo array.
Beh partiamo dall'inizio.
Se è quello che stiamo cercando, siamo in grado di fermare.
E 'no, non stiamo cercando 11.
Quindi in caso contrario, passare all'elemento successivo.
>> Quindi guardiamo a 23.
È 23 quello che stiamo cercando?
Beh no, così si passa a quello successivo elemento e l'elemento successivo,
e continuiamo attraverso questo processo più e più
e più volte, fino a quando atterriamo su una situazione come questa.
>> Nove è quello che stiamo cercando, e questo elemento dell'array
è, il suo valore è di nove.
E così abbiamo trovato ciò che siamo cercando, e siamo in grado di fermare.
La ricerca lineare ha completato, con successo.
>> Ma che dire se stiamo cercando un elemento che non è nella nostra gamma.
Ha ricerca lineare ancora lavorare?
Beh certo.
Quindi ripetiamo il processo a partire dal primo elemento.
Se è quello che stiamo cercando, siamo in grado di fermare.
Non è.
In caso contrario, ci spostiamo all'elemento successivo.
>> Ma possiamo continuare a ripetere questo processo, esaminando ogni elemento, a sua volta,
sperando che troviamo il numero 50.
Ma non sapremo se abbiamo trovato il numero 50
o se non lo facessimo, finché non avremo fatto un passo su ogni singolo elemento della matrice.
>> Solo una volta che abbiamo fatto che e venuto a breve,
possiamo concludere che 50 non è nella matrice.
E così la ricerca lineare algoritmo, beh non è riuscito, di per sé.
Ma non nel senso che non è riuscita a fare ciò che
abbiamo chiesto di fare.
>> E 'stato infruttuoso come tanto quanto non ha trovato 50,
ma 50 non era nella matrice.
Ma abbiamo cercato esaustivamente attraverso ogni singolo elemento
e così, mentre non abbiamo trovato qualsiasi cosa, ricerca lineare ancora
riesce anche se il elemento non è nell'array.
>> Allora qual è il caso peggiore scenario con la ricerca lineare?
Beh, dobbiamo guardare attraverso ogni singolo elemento,
sia perché l'elemento di destinazione è l'ultimo elemento dell'array,
o l'elemento che stiamo cercando non lo fa effettivamente esistenti nell'array affatto.
Qual è la migliore delle ipotesi?
Beh potremmo trovare il elemento immediatamente.
E quanti elementi dobbiamo quindi dobbiamo guardare
al nel migliore dei casi, se stiamo cercando per esso
e lo troviamo proprio all'inizio?
Siamo in grado di arrestare immediatamente.
>> Che cosa dice questo circa la complessità della ricerca lineare?
Beh, nel caso peggiore, abbiamo guardare ogni singolo elemento.
E così viene eseguito in O n, nel caso peggiore.
>> Nel migliore dei casi, stiamo andando immediatamente trovare l'elemento.
E così viene eseguito in omega di 1.
>> Sono Doug Lloyd.
Questo è CS50.