>> [REPRODUCCIÓN DE MÚSICA]
DOUG LLOYD: Lineal búsqueda es un algoritmo que
puede utilizar para encontrar un elemento en una matriz.
Un recuerdo algoritmo es un conjunto paso a paso
de instrucciones para completar una tarea.
>> La búsqueda lineal algoritmo funciona de la siguiente manera.
Iterar a través de la matriz de izquierda a derecha, en busca de un elemento especificado.
>> En pseudocódigo, que es un más versión destilada de esta frase,
si el primer elemento es lo que usted está buscando, puede detener.
De lo contrario, pasar al siguiente elemento y seguir adelante y otra vez hasta que encuentre
el elemento, o no lo haces.
Así que podemos usar el lineal algoritmo de búsqueda, por ejemplo,
para encontrar el valor objetivo nueve en esta matriz.
Bueno empecemos por el principio.
Si es lo que estamos buscando, podemos detener.
¡No es, no estamos buscando 11.
Así que de lo contrario, pasar al siguiente elemento.
>> Así que nos fijamos en el 23.
Es de 23 lo que estamos buscando?
Pues no, así que pasamos a la siguiente elemento, y el siguiente elemento,
y seguimos pasando por este proceso una y otra
y otra vez, hasta que aterricemos en una situación como esta.
>> Nueve es lo que estamos buscando, y este elemento de la matriz
es decir, su valor es de nueve.
Y así nos encontramos lo que estamos buscando, y podemos parar.
La búsqueda lineal tiene Completado satisfactoriamente.
>> Pero ¿qué pasa si estamos buscando un elemento que no está en nuestra matriz.
¿Tiene todavía trabajan búsqueda lineal?
Bien seguro.
Así que repetimos este proceso comenzando en el primer elemento.
Si es lo que estamos buscando, podemos detener.
No es.
De lo contrario, nos movemos al siguiente elemento.
>> Pero podemos seguir repitiendo este proceso, examinar cada elemento, a su vez,
la esperanza de que nos encontramos con el número 50.
Pero no vamos a saber si hemos encontrado el número 50
o si no lo hiciéramos, hasta que hayamos entramos sobre cada elemento de la matriz.
>> Sólo una vez que hemos hecho eso y se quedan cortos,
podemos concluir que 50 no está en el array.
Y por lo que la búsqueda lineal algoritmo, así que no, per se.
Pero no en el sentido de que no tuvo éxito en hacer lo que
pedimos que haga.
>> Se tuvo éxito en lo mucho más, ya que no se encontró 50,
pero 50 no estaba en el array.
Pero hemos buscado exhaustivamente a través de cada elemento
y así, mientras que no encontramos nada, búsqueda lineal todavía
tiene éxito incluso si la elemento no está en la matriz.
>> ¿Cuál es el peor de los casos escenario con búsqueda lineal?
Bueno, tenemos que mirar a través de cada elemento,
ya sea porque el elemento de destino es el último elemento de la matriz,
o el elemento que estamos buscando no en realidad existe en la matriz en absoluto.
¿Cuál es el mejor de los casos?
Bien podríamos encontrar la elemento inmediatamente.
¿Y cuántos elementos Cómo podemos entonces tenemos que mirar
en en el mejor caso, si estamos en busca de ella
y nos encontramos en el comienzo?
Podemos parar inmediatamente.
>> ¿Qué dice esto acerca de la complejidad de búsqueda lineal?
Bueno, en el peor de los casos, tenemos para mirar a cada elemento.
Y lo que se ejecuta en O de n, en el peor de los casos.
>> En el mejor de los casos, vamos a encontrar el elemento inmediatamente.
Y así funciona en omega de 1.
>> Soy Doug Lloyd.
Esto es CS50.