1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Busca lineal]

2
00:00:02,430 --> 00:00:04,430
[Patrick Schmid, da Universidade de Harvard]

3
00:00:04,430 --> 00:00:07,430
[Esta é CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Buscar é algo que probablemente facer máis veces do que pensa.

5
00:00:09,440 --> 00:00:11,600
Obviamente, cada vez que abrir un navegador

6
00:00:11,600 --> 00:00:12,890
e busca dunha páxina web -

7
00:00:12,890 --> 00:00:15,620
ou procura dos seus amigos no seu sitio web de redes sociais -

8
00:00:15,620 --> 00:00:16,610
está a procurar.

9
00:00:16,610 --> 00:00:19,690
Pero isto é só unha pequena parte da investigación que fai nunha base diaria.

10
00:00:19,690 --> 00:00:21,720
Cando quere atopar esa camisa dun azul no armario,

11
00:00:21,720 --> 00:00:23,620
ou blusa que vermella perfecta para a ocasión,

12
00:00:23,620 --> 00:00:24,730
está a procurar.

13
00:00:24,730 --> 00:00:26,640
Cando vai a unha tenda que nunca estivo antes,

14
00:00:26,640 --> 00:00:28,590
e está mirando para o brócolis no corredor do produto

15
00:00:28,590 --> 00:00:29,650
está a procurar.

16
00:00:29,650 --> 00:00:31,050
O que podes comezar a notar

17
00:00:31,050 --> 00:00:32,820
é que, dependendo do que está a buscar

18
00:00:32,820 --> 00:00:35,340
ou como os elementos son organizados cando está mirando para eles

19
00:00:35,340 --> 00:00:37,670
ten un efecto sobre como buscar.

20
00:00:37,670 --> 00:00:40,990
Por exemplo, se as súas camisas están colgadas no armario,

21
00:00:40,990 --> 00:00:42,840
pode ser só pegalo sen moita demanda.

22
00:00:42,840 --> 00:00:45,300
Se está asumindo que ten que camiñar ata o altar

23
00:00:45,300 --> 00:00:48,750
para obter o brócolis, probabelmente vostede ten que ollar para os outros vexetais

24
00:00:48,750 --> 00:00:49,940
antes de pensar que o brócolis.

25
00:00:49,940 --> 00:00:54,320
Busca lineal é un exemplo dun método de investigación de tales - ou algoritmo.

26
00:00:54,320 --> 00:00:55,550
Como o nome indica,

27
00:00:55,550 --> 00:00:59,240
Este método de investigación para un elemento dunha forma lineal, unha despois da outra.

28
00:00:59,240 --> 00:01:02,080
Entón, cando está mirando para os resultados do seu motor de procura favorito

29
00:01:02,080 --> 00:01:03,850
e que le a lista de resultados,

30
00:01:03,850 --> 00:01:05,290
está a usar procura lineal.

31
00:01:05,290 --> 00:01:06,830
Okay. Vexamos un exemplo.

32
00:01:06,830 --> 00:01:12,600
Dicir que temos unha lista de números - 2, 4, 0, 5, 3, 7, 8, e 1 -

33
00:01:12,600 --> 00:01:15,100
e nós estamos mirando para o número 0.

34
00:01:15,100 --> 00:01:17,290
Obviamente, pode só ver que a 0 está na terceira posición.

35
00:01:17,290 --> 00:01:19,790
Pero, un programa de ordenador non é que a sorte.

36
00:01:19,790 --> 00:01:22,030
Só pode "ver" a un número cada vez.

37
00:01:22,030 --> 00:01:23,840
Así, a partir do inicio da lista,

38
00:01:23,840 --> 00:01:25,000
el só "ve" o 2.

39
00:01:25,000 --> 00:01:27,860
O programa comproba entón - é igual a 2 0?

40
00:01:27,860 --> 00:01:30,320
Obviamente que non. Por iso, vai ao seguinte número 4.

41
00:01:30,320 --> 00:01:33,320
Fai 4 0 iguais? Nope.

42
00:01:33,320 --> 00:01:35,460
O seguinte, 0. Ah! Cero é igual a 0.

43
00:01:35,460 --> 00:01:36,920
Non temos iso! É na terceira posición.

44
00:01:36,920 --> 00:01:39,660
Okay. Vexamos algúns pseudocódigo.

45
00:01:39,660 --> 00:01:43,320
É só un par de liñas longas, pero imos ollar para el unha liña de cada vez.

46
00:01:43,320 --> 00:01:46,740
En primeiro lugar, imos definir a función - e nós imos chamalo de procura lineal -

47
00:01:46,740 --> 00:01:49,040
e leva dous argumentos - chave e matriz.

48
00:01:49,040 --> 00:01:50,770
A clave é que o valor que estamos a buscar,

49
00:01:50,770 --> 00:01:53,160
polo tanto, no exemplo anterior, que foi a cero.

50
00:01:53,160 --> 00:01:55,080
Unha matriz é unha lista de números

51
00:01:55,080 --> 00:01:57,180
que ten todos os valores que nós imos buscar.

52
00:01:57,180 --> 00:02:00,010
Entón, o que queremos facer é que queremos ollar -

53
00:02:00,010 --> 00:02:02,030
a partir de todas as posicións, así comezando no inicio da matriz

54
00:02:02,030 --> 00:02:05,260
ata o fin da matriz - de xeito que a lonxitude da matriz -

55
00:02:05,260 --> 00:02:07,580
mirar para cada posición única e comprobar cada unha.

56
00:02:07,580 --> 00:02:10,000
Entón é iso que que "a" loop está facendo.

57
00:02:10,000 --> 00:02:11,150
E en cada posición, imos dicir

58
00:02:11,150 --> 00:02:15,010
"É que o valor en que a actual posición igual á clave que estamos a buscar?"

59
00:02:15,010 --> 00:02:17,000
Así - no exemplo anterior de novo a tecla foi de 0 -

60
00:02:17,000 --> 00:02:21,770
por iso estamos dicindo que "é a matriz na posición i igual a cero?"

61
00:02:21,770 --> 00:02:24,640
Se for, imos voltar 'i' porque esa é a posición actual estamos.

62
00:02:24,640 --> 00:02:25,710
Así, no exemplo anterior,

63
00:02:25,710 --> 00:02:27,250
que foi a terceira posición.

64
00:02:27,250 --> 00:02:29,330
Se xa pasou por toda a matriz

65
00:02:29,330 --> 00:02:30,690
e non atopamos nada -

66
00:02:30,690 --> 00:02:32,180
entón imos dicir que estabamos a buscar ao número 500

67
00:02:32,180 --> 00:02:33,860
o que claramente non estaba naquel exemplo -

68
00:02:33,860 --> 00:02:35,860
temos que volver algo,

69
00:02:35,860 --> 00:02:37,140
e nós estamos indo para voltar -1.

70
00:02:37,140 --> 00:02:39,750
E estamos só retornando -1 porque é unha posición

71
00:02:39,750 --> 00:02:40,990
que non existe na matriz.

72
00:02:40,990 --> 00:02:43,940
E o que significa que cando recibe de volta dunha función

73
00:02:43,940 --> 00:02:46,500
el di que "Hmm, todo ben. Creo que non atopou nada.

74
00:02:46,500 --> 00:02:47,930
Para que nunca 500 estaba alí. "

75
00:02:47,930 --> 00:02:49,700
O agradable sobre a procura lineal é que

76
00:02:49,700 --> 00:02:51,060
vai traballar en calquera lista de elementos,

77
00:02:51,060 --> 00:02:52,950
independentemente da forma na que os elementos son ordenados.

78
00:02:52,950 --> 00:02:55,540
Non importa onde o brócolis é no corredor do produto.

79
00:02:55,540 --> 00:02:57,070
Mentres anda polo corredor, desde o principio ata o final,

80
00:02:57,070 --> 00:02:58,470
vostede está obrigado a atopalo,

81
00:02:58,470 --> 00:03:00,800
asumindo que a tenda non está sen brócolis, por suposto.

82
00:03:00,800 --> 00:03:04,200
Pero é a maior forza é tamén a súa maior debilidade.

83
00:03:04,200 --> 00:03:05,340
Digamos que ten unha lista de 200 números

84
00:03:05,340 --> 00:03:06,930
que están ordenados de 1 a 200.

85
00:03:06,930 --> 00:03:09,420
Se está a buscar para o número 198,

86
00:03:09,420 --> 00:03:11,060
ten que buscar case toda a lista de números

87
00:03:11,060 --> 00:03:12,960
antes de atopar o que está a procurar.

88
00:03:12,960 --> 00:03:14,460
Debe haber un xeito mellor!

89
00:03:14,460 --> 00:03:15,890
Asegúrese de que existe.

90
00:03:15,890 --> 00:03:17,440
Pero, iso é asunto para outro vídeo.

91
00:03:17,440 --> 00:03:19,280
Ademais, non se preocupe!

92
00:03:19,280 --> 00:03:22,650
Só porque busca lineal non é a mellor solución en todas as situacións,

93
00:03:22,650 --> 00:03:24,190
iso non significa que non vén a cadra.

94
00:03:24,190 --> 00:03:27,130
Se non, como cre que o brócolis no corredor do produto?

95
00:03:27,130 --> 00:03:29,910
O meu nome é Patrick Schmid, e este é o CS50.

96
00:03:29,910 --> 00:03:32,000
[CS50.TV]