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