Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Búsqueda Lineal]
[Patrick Schmid, Harvard University]
[Esta es CS50.] [CS50.TV]
La búsqueda es algo que probablemente haga más a menudo de lo que crees.
Obviamente, cada vez que abra un navegador web
y la búsqueda de una página web -
o búsqueda de tus amigos en tu red social favorita -
que está buscando.
Pero eso es sólo una pequeña parte de la búsqueda que usted hace sobre una base diaria.
Cuando desee encontrar que una camisa azul en el armario,
o esa blusa roja perfecta para la ocasión,
usted está buscando.
Cuando usted va a una tienda que nunca has estado antes,
y que está buscando para el brócoli en el pasillo de productos
usted está buscando.
Lo que pudo haber comenzado a notar
es que dependiendo de lo que estás buscando
o cómo los elementos se organizan cuando usted está buscando para ellos
tiene un efecto en cómo usted busca.
Por ejemplo, si sus camisas están colgando en el armario,
usted probablemente puede recogerlo sin mucho buscar.
Si usted está asumiendo que usted tiene que caminar por el pasillo
para obtener el brócoli, es probable que tenga que mirar a todos los otros vegetales
antes de encontrar que el brócoli.
La búsqueda lineal es un ejemplo de un método tal búsqueda - o algoritmo.
Como el nombre implica,
este método busca de un artículo de una forma lineal, una después de la otra.
Por lo tanto, cuando usted está buscando en los resultados de su motor de búsqueda favorito
y leer la lista de resultados,
usted está utilizando una búsqueda lineal.
Bien. Veamos un ejemplo.
Supongamos que tenemos una lista de números - 2, 4, 0, 5, 3, 7, 8, y 1 -
y estamos buscando el número 0.
Obviamente, usted puede ver que el 0 se encuentra en la tercera posición.
Pero, un programa de ordenador no es tan afortunado.
Sólo se puede "ver" un número a la vez.
Así, comenzando al principio de la lista,
sólo "ve" el 2.
Entonces, el programa comprueba - 2 es igual a 0?
Obviamente no. Así son las cosas en el siguiente número, 4.
¿Tiene 4 0 iguales? Nope.
El siguiente, 0. ¡Ah! Cero es igual a 0.
Ahí lo tenemos! Está en la tercera posición.
Bien. Echemos un vistazo a algunos pseudocódigo.
Es sólo un par de líneas largas, pero vamos a ver que una línea a la vez.
En primer lugar, vamos a definir la función - y vamos a llamarlo búsqueda lineal -
y toma dos argumentos - clave y matriz.
La clave es que el valor que estamos buscando,
Así en el ejemplo anterior, que era el cero.
Una matriz es una lista de números
que tiene todos los valores que vamos a buscar.
Así que lo que quiero hacer es que queremos ver -
desde todas las posiciones, por lo que a partir de los inicios de la matriz
hasta el final de la matriz - por lo que la longitud de la matriz -
mirar cada sola posición y comprobar cada uno.
Así que eso es lo que "para" bucle está haciendo.
Y en cada posición, vamos a decir
"¿Es ese valor en esa posición actual es igual a la clave que estamos buscando?"
Por lo tanto - en el ejemplo anterior, una vez más, la clave fue de 0 -
por lo que estamos diciendo "es la matriz en la posición i es igual a cero?"
Si es así, vamos a volver "i" porque esa es la posición actual estamos.
Así, en el ejemplo anterior,
que era la tercera posición.
Si hemos pasado por toda la matriz
y no hemos encontrado nada -
así que vamos a decir que estábamos buscando para el número 500
que claramente no era en ese ejemplo -
tenemos que devolver algo,
y vamos a devolver -1.
Y sólo estamos devolviendo -1 porque es una posición
que no existe en la matriz.
Y eso significa que cuando te lo devuelve de una función
dice "Hmm, está bien. Supongo que no encontraron nada.
Así que nunca 500 estaba allí. "
Lo bueno es que la búsqueda lineal
que va a trabajar en cualquier lista de elementos,
independientemente de cómo se ordenan los elementos.
No importa que el brócoli está en el pasillo de las verduras.
Mientras usted camina por el pasillo desde el principio hasta el final,
que está obligado a encontrar,
suponiendo que la tienda no se ha acabado de brócoli, por supuesto.
Pero es la mayor fortaleza es también su mayor debilidad.
Digamos que usted tiene una lista de 200 números
que están ordenadas desde 1 hasta 200.
Si usted está buscando para el número 198,
tienes que buscar casi toda la lista de números
antes de encontrar el que usted está buscando.
Tiene que haber una manera mejor!
Tenga la seguridad de que existe.
Pero eso es tema para otro video.
Además, no se preocupe!
El hecho de que la búsqueda lineal no es la mejor solución para todas las situaciones,
eso no quiere decir que no son útiles.
De lo contrario, ¿cómo te encuentras con que el brócoli en el pasillo de productos?
Mi nombre es Patrick Schmid, y esto es CS50.
[CS50.TV]