1
00:00:00,000 --> 00:00:02,892
>> [Jouer de la musique]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linéaire
la recherche est un algorithme de nous

4
00:00:07,180 --> 00:00:09,840
peut utiliser pour trouver un élément dans un tableau.

5
00:00:09,840 --> 00:00:11,990
Un rappel de l'algorithme
est un ensemble étape par étape

6
00:00:11,990 --> 00:00:15,030
des instructions pour remplir une tâche.

7
00:00:15,030 --> 00:00:17,480
>> La recherche linéaire
algorithme fonctionne comme suit.

8
00:00:17,480 --> 00:00:22,200
Itérer à travers la matrice de gauche à
à droite, la recherche d'un élément spécifié.

9
00:00:22,200 --> 00:00:26,380
>> Dans pseudo, ce qui est un plus
la version distillée de cette phrase,

10
00:00:26,380 --> 00:00:29,840
si le premier élément est ce que
vous cherchez, vous pouvez vous arrêter.

11
00:00:29,840 --> 00:00:33,930
Sinon, passer à l'élément suivant et
continuer encore et encore jusqu'à ce que vous trouvez

12
00:00:33,930 --> 00:00:36,389
l'élément, ou vous ne le faites pas.

13
00:00:36,389 --> 00:00:38,680
Donc, nous pouvons utiliser le linéaire
algorithme de recherche, par exemple,

14
00:00:38,680 --> 00:00:42,330
pour trouver la valeur cible
neuf dans ce tableau.

15
00:00:42,330 --> 00:00:43,870
Eh bien, nous commençons par le début.

16
00:00:43,870 --> 00:00:45,970
Si elle est ce que nous sommes
cherchez, nous pouvons nous arrêter.

17
00:00:45,970 --> 00:00:47,890
Il est pas, nous ne sommes pas à la recherche de 11.

18
00:00:47,890 --> 00:00:50,220
Donc, autrement, passer à l'élément suivant.

19
00:00:50,220 --> 00:00:51,510
>> Donc, nous regardons à 23.

20
00:00:51,510 --> 00:00:52,730
Est de 23 ce que nous cherchons?

21
00:00:52,730 --> 00:00:55,614
Eh bien non, si nous passons à la prochaine
élément, et l'élément suivant,

22
00:00:55,614 --> 00:00:57,780
et nous continuons à travers
ce processus encore et encore

23
00:00:57,780 --> 00:01:01,030
et plus, jusqu'à ce que nous atterrissons
sur une situation de ce genre.

24
00:01:01,030 --> 00:01:03,910
>> Nine est ce que nous recherchons,
et cet élément de la matrice

25
00:01:03,910 --> 00:01:05,787
est, sa valeur est de neuf.

26
00:01:05,787 --> 00:01:08,120
Et donc nous avons trouvé ce que nous sommes
cherchez, et nous pouvons nous arrêter.

27
00:01:08,120 --> 00:01:11,910
La recherche linéaire a
complété, avec succès.

28
00:01:11,910 --> 00:01:15,370
>> Mais qu'en est-il si nous sommes à la recherche
un élément qui est pas dans notre tableau.

29
00:01:15,370 --> 00:01:17,040
Est-ce que la recherche linéaire fonctionne toujours?

30
00:01:17,040 --> 00:01:17,540
Bien sûr.

31
00:01:17,540 --> 00:01:19,947
Donc, nous répétons ce processus
en commençant par le premier élément.

32
00:01:19,947 --> 00:01:21,780
Si elle est ce que nous sommes
cherchez, nous pouvons nous arrêter.

33
00:01:21,780 --> 00:01:22,800
Ce n'est pas.

34
00:01:22,800 --> 00:01:25,020
Sinon, nous passons à l'élément suivant.

35
00:01:25,020 --> 00:01:29,050
>> Mais nous ne pouvons continuer à répéter ce processus,
examinant chaque élément à son tour,

36
00:01:29,050 --> 00:01:31,720
en espérant que nous trouvons le nombre 50.

37
00:01:31,720 --> 00:01:33,750
Mais nous ne saurons pas si
nous avons trouvé le numéro 50

38
00:01:33,750 --> 00:01:38,290
ou si nous ne l'avons pas, jusqu'à ce que nous avons franchi
sur chaque élément du tableau.

39
00:01:38,290 --> 00:01:40,440
>> Seulement une fois que nous avons fait
cela et trouver à court,

40
00:01:40,440 --> 00:01:43,040
pouvons-nous conclure que
50 ne figure pas dans le tableau.

41
00:01:43,040 --> 00:01:46,410
Et donc la recherche linéaire
algorithme, ainsi il n'a pas, en soi.

42
00:01:46,410 --> 00:01:49,181
Mais pas dans le sens où il
n'a pas réussi à faire ce que

43
00:01:49,181 --> 00:01:49,930
nous lui avons demandé de faire.

44
00:01:49,930 --> 00:01:52,390
>> Il a échoué en tant
autant qu'il n'a pas trouvé 50,

45
00:01:52,390 --> 00:01:54,070
mais 50 ne figurait pas dans le tableau.

46
00:01:54,070 --> 00:01:57,310
Mais nous avons exhaustivement recherché
à travers chaque élément

47
00:01:57,310 --> 00:02:00,550
et ainsi, alors que nous ne l'avons pas trouvé
quoi que ce soit, la recherche linéaire encore

48
00:02:00,550 --> 00:02:05,230
réussit même si le
élément se trouve pas dans le tableau.

49
00:02:05,230 --> 00:02:07,507
>> Alors, quel est le pire des cas
scénario avec recherche linéaire?

50
00:02:07,507 --> 00:02:09,590
Eh bien, nous avons de regarder à travers
chaque élément,

51
00:02:09,590 --> 00:02:14,590
soit parce que l'élément de cible
est le dernier élément du tableau,

52
00:02:14,590 --> 00:02:18,510
ou l'élément que nous recherchons ne
réellement exister dans le tableau du tout.

53
00:02:18,510 --> 00:02:19,760
Quel est le meilleur scénario?

54
00:02:19,760 --> 00:02:22,430
Eh bien, nous pourrions trouver le
élément immédiatement.

55
00:02:22,430 --> 00:02:24,360
Et combien d'éléments
avons-nous alors à regarder

56
00:02:24,360 --> 00:02:26,859
à dans le meilleur des cas,
si nous sommes à la recherche pour elle

57
00:02:26,859 --> 00:02:28,400
et nous trouvons au tout début?

58
00:02:28,400 --> 00:02:29,850
Nous pouvons cesser immédiatement.

59
00:02:29,850 --> 00:02:32,984
>> Qu'est-ce que cela nous dit sur la
complexité de la recherche linéaire?

60
00:02:32,984 --> 00:02:35,650
Eh bien, dans le pire des cas, nous avons
à regarder chaque élément.

61
00:02:35,650 --> 00:02:38,930
Et pour qu'il fonctionne dans O
n, dans le pire des cas.

62
00:02:38,930 --> 00:02:41,540
>> Dans le meilleur des cas, nous allons
trouver l'élément immédiatement.

63
00:02:41,540 --> 00:02:44,750
Et fonctionne en oméga de 1.

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

65
00:02:45,780 --> 00:02:48,020
Ceci est CS50.

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