1
00:00:00,000 --> 00:00:02,892
>> [REPRODUCCIÓN DE MÚSICA]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Lineal
búsqueda es un algoritmo que

4
00:00:07,180 --> 00:00:09,840
puede utilizar para encontrar un elemento en una matriz.

5
00:00:09,840 --> 00:00:11,990
Un recuerdo algoritmo
es un conjunto paso a paso

6
00:00:11,990 --> 00:00:15,030
de instrucciones para completar una tarea.

7
00:00:15,030 --> 00:00:17,480
>> La búsqueda lineal
algoritmo funciona de la siguiente manera.

8
00:00:17,480 --> 00:00:22,200
Iterar a través de la matriz de izquierda a
derecha, en busca de un elemento especificado.

9
00:00:22,200 --> 00:00:26,380
>> En pseudocódigo, que es un más
versión destilada de esta frase,

10
00:00:26,380 --> 00:00:29,840
si el primer elemento es lo
que usted está buscando, puede detener.

11
00:00:29,840 --> 00:00:33,930
De lo contrario, pasar al siguiente elemento y
seguir adelante y otra vez hasta que encuentre

12
00:00:33,930 --> 00:00:36,389
el elemento, o no lo haces.

13
00:00:36,389 --> 00:00:38,680
Así que podemos usar el lineal
algoritmo de búsqueda, por ejemplo,

14
00:00:38,680 --> 00:00:42,330
para encontrar el valor objetivo
nueve en esta matriz.

15
00:00:42,330 --> 00:00:43,870
Bueno empecemos por el principio.

16
00:00:43,870 --> 00:00:45,970
Si es lo que estamos
buscando, podemos detener.

17
00:00:45,970 --> 00:00:47,890
¡No es, no estamos buscando 11.

18
00:00:47,890 --> 00:00:50,220
Así que de lo contrario, pasar al siguiente elemento.

19
00:00:50,220 --> 00:00:51,510
>> Así que nos fijamos en el 23.

20
00:00:51,510 --> 00:00:52,730
Es de 23 lo que estamos buscando?

21
00:00:52,730 --> 00:00:55,614
Pues no, así que pasamos a la siguiente
elemento, y el siguiente elemento,

22
00:00:55,614 --> 00:00:57,780
y seguimos pasando por
este proceso una y otra

23
00:00:57,780 --> 00:01:01,030
y otra vez, hasta que aterricemos
en una situación como esta.

24
00:01:01,030 --> 00:01:03,910
>> Nueve es lo que estamos buscando,
y este elemento de la matriz

25
00:01:03,910 --> 00:01:05,787
es decir, su valor es de nueve.

26
00:01:05,787 --> 00:01:08,120
Y así nos encontramos lo que estamos
buscando, y podemos parar.

27
00:01:08,120 --> 00:01:11,910
La búsqueda lineal tiene
Completado satisfactoriamente.

28
00:01:11,910 --> 00:01:15,370
>> Pero ¿qué pasa si estamos buscando
un elemento que no está en nuestra matriz.

29
00:01:15,370 --> 00:01:17,040
¿Tiene todavía trabajan búsqueda lineal?

30
00:01:17,040 --> 00:01:17,540
Bien seguro.

31
00:01:17,540 --> 00:01:19,947
Así que repetimos este proceso
comenzando en el primer elemento.

32
00:01:19,947 --> 00:01:21,780
Si es lo que estamos
buscando, podemos detener.

33
00:01:21,780 --> 00:01:22,800
No es.

34
00:01:22,800 --> 00:01:25,020
De lo contrario, nos movemos al siguiente elemento.

35
00:01:25,020 --> 00:01:29,050
>> Pero podemos seguir repitiendo este proceso,
examinar cada elemento, a su vez,

36
00:01:29,050 --> 00:01:31,720
la esperanza de que nos encontramos con el número 50.

37
00:01:31,720 --> 00:01:33,750
Pero no vamos a saber si
hemos encontrado el número 50

38
00:01:33,750 --> 00:01:38,290
o si no lo hiciéramos, hasta que hayamos entramos
sobre cada elemento de la matriz.

39
00:01:38,290 --> 00:01:40,440
>> Sólo una vez que hemos hecho
eso y se quedan cortos,

40
00:01:40,440 --> 00:01:43,040
podemos concluir que
50 no está en el array.

41
00:01:43,040 --> 00:01:46,410
Y por lo que la búsqueda lineal
algoritmo, así que no, per se.

42
00:01:46,410 --> 00:01:49,181
Pero no en el sentido de que
no tuvo éxito en hacer lo que

43
00:01:49,181 --> 00:01:49,930
pedimos que haga.

44
00:01:49,930 --> 00:01:52,390
>> Se tuvo éxito en lo
mucho más, ya que no se encontró 50,

45
00:01:52,390 --> 00:01:54,070
pero 50 no estaba en el array.

46
00:01:54,070 --> 00:01:57,310
Pero hemos buscado exhaustivamente
a través de cada elemento

47
00:01:57,310 --> 00:02:00,550
y así, mientras que no encontramos
nada, búsqueda lineal todavía

48
00:02:00,550 --> 00:02:05,230
tiene éxito incluso si la
elemento no está en la matriz.

49
00:02:05,230 --> 00:02:07,507
>> ¿Cuál es el peor de los casos
escenario con búsqueda lineal?

50
00:02:07,507 --> 00:02:09,590
Bueno, tenemos que mirar a través de
cada elemento,

51
00:02:09,590 --> 00:02:14,590
ya sea porque el elemento de destino
es el último elemento de la matriz,

52
00:02:14,590 --> 00:02:18,510
o el elemento que estamos buscando no
en realidad existe en la matriz en absoluto.

53
00:02:18,510 --> 00:02:19,760
¿Cuál es el mejor de los casos?

54
00:02:19,760 --> 00:02:22,430
Bien podríamos encontrar la
elemento inmediatamente.

55
00:02:22,430 --> 00:02:24,360
¿Y cuántos elementos
Cómo podemos entonces tenemos que mirar

56
00:02:24,360 --> 00:02:26,859
en en el mejor caso,
si estamos en busca de ella

57
00:02:26,859 --> 00:02:28,400
y nos encontramos en el comienzo?

58
00:02:28,400 --> 00:02:29,850
Podemos parar inmediatamente.

59
00:02:29,850 --> 00:02:32,984
>> ¿Qué dice esto acerca de la
complejidad de búsqueda lineal?

60
00:02:32,984 --> 00:02:35,650
Bueno, en el peor de los casos, tenemos
para mirar a cada elemento.

61
00:02:35,650 --> 00:02:38,930
Y lo que se ejecuta en O de
n, en el peor de los casos.

62
00:02:38,930 --> 00:02:41,540
>> En el mejor de los casos, vamos a
encontrar el elemento inmediatamente.

63
00:02:41,540 --> 00:02:44,750
Y así funciona en omega de 1.

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

65
00:02:45,780 --> 00:02:48,020
Esto es CS50.

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