1
00:00:00,000 --> 00:00:02,892
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineare
di ricerca è un algoritmo di noi

4
00:00:07,180 --> 00:00:09,840
possono utilizzare per trovare un elemento in un array.

5
00:00:09,840 --> 00:00:11,990
Un richiamo algoritmo
è un insieme passo-passo

6
00:00:11,990 --> 00:00:15,030
di istruzioni per il completamento di un compito.

7
00:00:15,030 --> 00:00:17,480
>> La ricerca lineare
algoritmo funziona come segue.

8
00:00:17,480 --> 00:00:22,200
Scorrere attraverso la matrice da sinistra a
a destra, alla ricerca di un elemento specificato.

9
00:00:22,200 --> 00:00:26,380
>> In pseudocodice, che è un altro
versione distillata di questa frase,

10
00:00:26,380 --> 00:00:29,840
se il primo elemento è quello
che stai cercando, ci si può fermare.

11
00:00:29,840 --> 00:00:33,930
In caso contrario, passare all'elemento successivo e
andare avanti più e più volte fino a trovare

12
00:00:33,930 --> 00:00:36,389
l'elemento, o non fare.

13
00:00:36,389 --> 00:00:38,680
Così possiamo usare il lineare
algoritmo di ricerca, ad esempio,

14
00:00:38,680 --> 00:00:42,330
per trovare il valore bersaglio
nove in questo array.

15
00:00:42,330 --> 00:00:43,870
Beh partiamo dall'inizio.

16
00:00:43,870 --> 00:00:45,970
Se è quello che stiamo
cercando, siamo in grado di fermare.

17
00:00:45,970 --> 00:00:47,890
E 'no, non stiamo cercando 11.

18
00:00:47,890 --> 00:00:50,220
Quindi in caso contrario, passare all'elemento successivo.

19
00:00:50,220 --> 00:00:51,510
>> Quindi guardiamo a 23.

20
00:00:51,510 --> 00:00:52,730
È 23 quello che stiamo cercando?

21
00:00:52,730 --> 00:00:55,614
Beh no, così si passa a quello successivo
elemento e l'elemento successivo,

22
00:00:55,614 --> 00:00:57,780
e continuiamo attraverso
questo processo più e più

23
00:00:57,780 --> 00:01:01,030
e più volte, fino a quando atterriamo
su una situazione come questa.

24
00:01:01,030 --> 00:01:03,910
>> Nove è quello che stiamo cercando,
e questo elemento dell'array

25
00:01:03,910 --> 00:01:05,787
è, il suo valore è di nove.

26
00:01:05,787 --> 00:01:08,120
E così abbiamo trovato ciò che siamo
cercando, e siamo in grado di fermare.

27
00:01:08,120 --> 00:01:11,910
La ricerca lineare ha
completato, con successo.

28
00:01:11,910 --> 00:01:15,370
>> Ma che dire se stiamo cercando
un elemento che non è nella nostra gamma.

29
00:01:15,370 --> 00:01:17,040
Ha ricerca lineare ancora lavorare?

30
00:01:17,040 --> 00:01:17,540
Beh certo.

31
00:01:17,540 --> 00:01:19,947
Quindi ripetiamo il processo
a partire dal primo elemento.

32
00:01:19,947 --> 00:01:21,780
Se è quello che stiamo
cercando, siamo in grado di fermare.

33
00:01:21,780 --> 00:01:22,800
Non è.

34
00:01:22,800 --> 00:01:25,020
In caso contrario, ci spostiamo all'elemento successivo.

35
00:01:25,020 --> 00:01:29,050
>> Ma possiamo continuare a ripetere questo processo,
esaminando ogni elemento, a sua volta,

36
00:01:29,050 --> 00:01:31,720
sperando che troviamo il numero 50.

37
00:01:31,720 --> 00:01:33,750
Ma non sapremo se
abbiamo trovato il numero 50

38
00:01:33,750 --> 00:01:38,290
o se non lo facessimo, finché non avremo fatto un passo
su ogni singolo elemento della matrice.

39
00:01:38,290 --> 00:01:40,440
>> Solo una volta che abbiamo fatto
che e venuto a breve,

40
00:01:40,440 --> 00:01:43,040
possiamo concludere che
50 non è nella matrice.

41
00:01:43,040 --> 00:01:46,410
E così la ricerca lineare
algoritmo, beh non è riuscito, di per sé.

42
00:01:46,410 --> 00:01:49,181
Ma non nel senso che
non è riuscita a fare ciò che

43
00:01:49,181 --> 00:01:49,930
abbiamo chiesto di fare.

44
00:01:49,930 --> 00:01:52,390
>> E 'stato infruttuoso come
tanto quanto non ha trovato 50,

45
00:01:52,390 --> 00:01:54,070
ma 50 non era nella matrice.

46
00:01:54,070 --> 00:01:57,310
Ma abbiamo cercato esaustivamente
attraverso ogni singolo elemento

47
00:01:57,310 --> 00:02:00,550
e così, mentre non abbiamo trovato
qualsiasi cosa, ricerca lineare ancora

48
00:02:00,550 --> 00:02:05,230
riesce anche se il
elemento non è nell'array.

49
00:02:05,230 --> 00:02:07,507
>> Allora qual è il caso peggiore
scenario con la ricerca lineare?

50
00:02:07,507 --> 00:02:09,590
Beh, dobbiamo guardare attraverso
ogni singolo elemento,

51
00:02:09,590 --> 00:02:14,590
sia perché l'elemento di destinazione
è l'ultimo elemento dell'array,

52
00:02:14,590 --> 00:02:18,510
o l'elemento che stiamo cercando non lo fa
effettivamente esistenti nell'array affatto.

53
00:02:18,510 --> 00:02:19,760
Qual è la migliore delle ipotesi?

54
00:02:19,760 --> 00:02:22,430
Beh potremmo trovare il
elemento immediatamente.

55
00:02:22,430 --> 00:02:24,360
E quanti elementi
dobbiamo quindi dobbiamo guardare

56
00:02:24,360 --> 00:02:26,859
al nel migliore dei casi,
se stiamo cercando per esso

57
00:02:26,859 --> 00:02:28,400
e lo troviamo proprio all'inizio?

58
00:02:28,400 --> 00:02:29,850
Siamo in grado di arrestare immediatamente.

59
00:02:29,850 --> 00:02:32,984
>> Che cosa dice questo circa la
complessità della ricerca lineare?

60
00:02:32,984 --> 00:02:35,650
Beh, nel caso peggiore, abbiamo
guardare ogni singolo elemento.

61
00:02:35,650 --> 00:02:38,930
E così viene eseguito in O
n, nel caso peggiore.

62
00:02:38,930 --> 00:02:41,540
>> Nel migliore dei casi, stiamo andando
immediatamente trovare l'elemento.

63
00:02:41,540 --> 00:02:44,750
E così viene eseguito in omega di 1.

64
00:02:44,750 --> 00:02:45,780
>> Sono Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Questo è CS50.

66
00:02:48,020 --> 00:02:49,876