Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Ricerca lineare]
[Patrick Schmid, Harvard University]
[Questa è CS50.] [CS50.TV]
La ricerca è una cosa che probabilmente non più spesso di quanto si pensi.
Ovviamente, ogni volta che si apre un browser web
e la ricerca di una pagina web -
o la ricerca per i tuoi amici sul tuo sito di social network preferiti -
si sta cercando.
Ma questa è solo una piccola parte della ricerca che si fa su una base quotidiana.
Se si desidera trovare quella camicia blu nell'armadio,
o quella camicetta rosso perfetto per l'occasione,
che si sta cercando.
Quando si va in un negozio che non sei mai stato prima,
e stai cercando i broccoli nella navata prodotti
che si sta cercando.
Che cosa si può avere iniziato a notare
è che a seconda di ciò che stai cercando
o come gli elementi sono organizzati quando si è alla ricerca di loro
ha un effetto su come si esegue una ricerca.
Ad esempio, se le magliette sono appesi nell'armadio,
probabilmente si può semplicemente scegliere senza molte ricerche.
Se stai assumendo bisogna camminare lungo la navata
per ottenere i broccoli, probabilmente dovete guardare tutte le altre verdure
prima di trovare che i broccoli.
Ricerca lineare è un esempio di un tale metodo ricerca - o algoritmo.
Come suggerisce il nome,
questo metodo cerca un elemento in modo lineare, uno dopo l'altro.
Così, quando si sta guardando i risultati di un motore di ricerca
e di leggere la lista dei risultati,
si utilizza ricerca lineare.
Va bene. Vediamo un esempio.
Dire che abbiamo un elenco di numeri - 2, 4, 0, 5, 3, 7, 8, e 1 -
e stiamo cercando il numero 0.
Ovviamente, si può notare che i 0 è nella terza posizione.
Ma, un programma per computer non è così fortunato.
Si può solo "vedere" un numero alla volta.
Quindi, a partire dall'inizio della lista,
solo "vede" il 2.
Il programma verifica quindi - è 2 pari a 0?
Ovviamente no. Così si va avanti al numero successivo, 4.
Fa 4 0 uguali? Nope.
Il prossimo, 0. Ah! Zero è uguale a 0.
Non ce l'abbiamo! E 'in terza posizione.
Va bene. Diamo un'occhiata a un po 'di pseudocodice.
E 'solo un paio di righe lunghe, ma diamo un'occhiata a che una riga alla volta.
Per prima cosa, definire la funzione - e abbiamo intenzione di chiamarlo ricerca lineare -
e ci vogliono due argomenti - chiave e array.
La chiave è che il valore che stiamo cercando,
così nell'esempio precedente, che era lo zero.
Una matrice è un elenco di numeri
che ha tutti i valori che stiamo andando alla ricerca.
Quindi, quello che vogliamo fare è che vogliamo guardare -
da tutte le posizioni, in modo da partire dall'inizio della matrice
fino alla fine della matrice - così la lunghezza della matrice -
guardare ogni singola posizione e controllare ognuno.
Quindi questo è quello che che "per" loop sta facendo.
E in ogni posizione, andremo a dire
"E 'quel valore in quella posizione corrente pari alla chiave che stiamo cercando?"
Così - nel precedente esempio di nuovo, la chiave era 0 -
quindi stiamo dicendo "E 'la matrice nella posizione i uguale a zero?"
Se lo è, stiamo per tornare 'i', perché questo è l'attuale posizione che ci siamo.
Così, nell'esempio precedente,
che era la terza posizione.
Se abbiamo passato l'intera matrice
e non abbiamo trovato nulla -
quindi diciamo che stavamo cercando il numero 500
che evidentemente non era in quella lista -
dobbiamo restituire qualcosa,
e abbiamo intenzione di tornare -1.
E siamo solo restituisce -1 perché è una posizione
che non esiste nella matrice.
E così questo significa che, quando lo si ottiene indietro da una funzione
si dice "Hmm, ok. Credo che non ho trovato niente.
In modo che non è mai 500 era lì. "
La cosa bella è che la ricerca lineare
che funzionerà su qualsiasi lista di elementi,
indipendentemente da come gli elementi sono ordinati.
Non importa dove i broccoli è nella navata prodotti.
Fino a quando si cammina lungo la navata dal principio alla fine,
sei destinato a trovare,
supponendo che il negozio non è a corto di broccoli, naturalmente.
Ma è più grande forza è anche la sua più grande debolezza.
Diciamo che avete una lista di 200 numeri
che sono ordinati 1-200.
Se stai cercando per il numero 198,
si deve cercare quasi l'intero elenco di numeri
prima di trovare quello che state cercando.
Ci deve essere un modo migliore!
Siate certi che ci sia.
Ma, questo è un argomento per un altro video.
Inoltre, non preoccupatevi!
Solo perché ricerca lineare non è la soluzione migliore in tutte le situazioni,
ciò non significa che essa non tornare utile.
In caso contrario, come si scopre che i broccoli nella navata prodotti?
Il mio nome è Patrick Schmid, e questo è CS50.
[CS50.TV]