Algoritmos de Búsqueda y Ordenación: Búsqueda Lineal en Python
Contenido del curso
Bryan Duarte
jesus alberto negrin guerrero
Aitor Zaldua
Michelle Osorio
Ricardo Rito Anguiano
Cesar Hernández Ramírez
Said Leonardo
Mauricio Gonzalez Falcon
Erick Alay
Danilo Toro
freddy molleda
Fredy Alberto Orozco Loaiza
Luis Enrique Huamán Quispe
Franco Giacometti
Platzi Team
Adrian Stiven Jimenez Cardenas
Gabriel Missael Barco
Fidel Hernández Rendón
Helard Flores
Ariadna B
Cecilia Natali Pilco Padilla
- -
Hector F
Christian Sanclemente
Edgar Eusebio Marin Parra
Massimo Di Berardino
Edgar Eusebio Marin Parra
Geraldine León
jesus alberto negrin guerrero
Antony Samuel Brenes Cruz
Luis Fernando Pedroza Taborda
Andrés David Solarte Vidal
Clayton Jhordan Iliquin Zavaleta
Josue Noha Valdivia
Miguel Torres
Angel Estrada
Cesar Hernández Ramírez
Angel Solis
Eber Laurente Lliuyacc
Andres Troaños
Mauro Nava
Eddy Arellanes
Daniel Guarín García
Cristian Antonio García González
Daniel Guarín García
GUADALUPE GARCÍA VÁZQUEZ
Si a alguien le aparece el siguiente error
NameError: name 'random' is not defined
coloquen lo siguiente al inicio del código
import random
:)
eso es lo bueno de ejecutar el problema con la consola, que siempre te indica porque el error, la consola te indicaba que random no estaba definido que existia un error, al no ser una variable y ser un modulo tenemos que invocarlo siempre.
gracias @bryanjavier, efectivamente me dio ese error, me has ahorrado un buen tiempo de búsqueda.
Wowwww, no sabia lo de poner el if en la cadena. Python es lo mejor.
En otros lenguajes lo encuentras algo asi como match = found? "is" : "isn't";
x2 Bro
Intente ver que sucedía se si hacia más grande la lista y el rango de números aleatorios.
Fue mala idea imprimir la lista
Casi explota tu laptop :o, estaba como corran porque voy a explotar :exclamation: Bueno al menos eso deja claro como funciona O(n)
Como puedo saber la complejidad algoritmica si reemplazo por esta función?
def busqueda_lineal(lista, objetivo): return objetivo in lista
Es bastante más limpio el código como lo estas planteando pero la complejidad algoritmica seria la misma ya que internmente python aplica la función iter() al objeto iterable "lista" para obtener cada elemento y la compara con la variable "objetivo" para devolver un false o un true. . Eso quiere decir que aplicariamos la mismas iteraciones a lo largo del tiempo, un O(n) en Big oh notation. iteraciones definidas por el tamaño del objeto iterable y recuerda que para definir la complejidad de un algoritmo tomamos el peor de los casos es decir cuando se recorre el objeto iterable por completo. . En la documentacion de python, en la direccion que comparte @danielfernando, lo dice directamente. Las expresiones con la forma < X in S > tienen una complejidad O(n)
tendrias o(n), porque depende del tamaño de la lista, se puede decir que en el fondo estás utilizando un for loop
Les dejo el código de la clase, buen día
import random def busqueda_lineal(lista, objetivo): match = False for elemento in lista: # O(n) if elemento == objetivo: match = True break return match if __name__ == '__main__': tamano_lista = int(input('De que tamaño sera la lista? : ')) objetivo = int(input('¿Que numeor quieres encontrar?')) lista = [random.randint(0,100) for i in range(tamano_lista)] encontrado = busqueda_lineal(lista, objetivo) print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista ')
Gracias, me estaba volviendo loco porque tenía el codigo igual pero me saltaba un error en el ultimo print de que no estaba cerrando el ( ) Era que yo utilizaba siempre comillas dobles en lugar de las comillas simples para todo lo que esta fuera del if
Ternarios vs ifs El operador ternario en python es relativamente reciente, apareció en la versión 2.5 y es el siguiente:
"A" if True else "B" 'A' "A" if False else "B" 'B' Es una forma abreviada del if que funciona como expresión (se evalúa y devuelve un valor).
La forma general es:
VALOR1 if CONDICION else VALOR2 Si CONDICION es verdadera, entonces la expresión devuelve VALOR1, si no, devuelve VALOR2.
¿Cuál es el problema del operador ternario?
Sólo se puede usar cuando no te importe no ser compatible con python 2.4. Acordáte que hay (y va a haber hasta el 2013 por lo menos) versiones de Linux en amplio uso con python 2.4
Si ignoramos eso, hay casos en los que simplifica mucho el código. Tomemos el ejemplo de un argumento por default, de un tipo modificable a una función. Ésta es la versión clásica:
class c: def f(self, arg = None): if arg is None: self.arg = [] else: self.arg = arg Y esta es la versión “moderna”:
class c: def f(self, arg = None): self.arg = 42 if arg is None else arg ¿La ventaja? ¡Se lee de corrido! “self.arg es 42 si arg es None, si no, es arg”
muy buen aporte , ya me estaba frustrandoo por no enterder eso gracias :)
Notas de al sesión :smile: Búsqueda lineal.
if elsedirectamente en una sola línea de código, para ello la sintaxis es en general (en un f-string) {<operaciones> if <condiciones> else <operaciones>}.import random def busqueda_lineal(lista, objetivo): match = False for i, elemento in enumerate(lista): if elemento == objetivo: match = True break return match if __name__ == '__main__': tamano_de_lista = int(input('Tamaño de la lista?: ')) objetivo = int(input('Que numero entero quieres encontrar: ')) lista = [random.randint(0, 100) for i in range(tamano_de_lista)] encontrado = busqueda_lineal(lista, objetivo) print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
Alguien sabe por qué la primer línea de código no me funciona? siempre se va a no encontrado así esté en la lista. Ocupé el segundo y me funciona bien.
print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista') print('El elemento {} {} en la lista'.format(objetivo, "esta" if objetivo else "no esta"))
Estas usando la ultima version de python?
Creo que tu versión de python es anterior a la 3.6. Por que fue en python 3.6 donde se implementó los f-strings
BUSQUEDA LINEAL Mejor Caso: Cuando el elemento se encuentra en la primera posición quiere decir que solo realiza 1 iteración el bucle for por lo tanto su complejidad es O(1) Peor Caso: Cuando el elemento se encuentra en la ultima posición o no se encuentra dentro del array -> O(n)
IMPLEMENTACIÓN DE LA CLASE
import random # Algoritmo de Busqueda def linear_search(lista , objetivo): match = False # Bucle Principal for elemento in lista : # O(n) -> Depende del tamaño de la lista if elemento == objetivo: match = True break return match if __name__ == "__main__": t = int(input("Tamanno de Lista: ")) listx = [random.randint(0,100) for i in range(t)] obj = int(input("Objetivo: ")) print(listx) encontrado = linear_search(listx , obj) print(f'El elemento {obj} {"esta" if encontrado else "no esta"} en la lista') # Controlar comillas para no generar ambiguedad
IMPLEMENTACIÓN EN PYTHON
def linear_search(ltx,srch): for i in range(len(ltx)-1): if (srch == ltx[i]): return i return -1 lista = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30] res0 = linear_search(lista,1) print(res0) # 0
IMPLEMENTACIÓN EN C++
#include <iostream> using namespace std; int search(int arr[], int n, int x) { int i ; for (i = 0; i < n; i++) if (arr[i] == x) return i ; return -1 ; } int main(){ int arr[] = { 2, 3, 4, 10, 40 } ; int x = 10 ; int n = sizeof(arr) / sizeof(arr[0]) ; int result = search(arr, n, x); (result == -1) ? cout << "Element is not present in array" : cout << "Element is present at index " << result; return 0; }
¿Por qué la probabilidad de que aparezca el numero incrementa cuando el numero posible de casos es mayor (generacion de numeros random en el array) si la formula de probabilidad es casos favorables/casos posibles?
Teoricamente mientras mas incremente el numero de casos posibles, de 5 a 100 por ejemplo, la probabilidad deberia disminuir ya que seria de 1/5 a 1/100. Pero en la práctica vemos que esto es distinto ya que a mayor cantidad de elementos en el array generados randomente, es mas probable que aparezca un elemento específico que estamos buscando.
Espero sepan responderme! jaja
Gracias.
Lo que sucede es que no estás hablando de lo mismo.
Piensa que crearas una lista números enteros aleatorios entre 0 y 3. La probabilidad de que encuentres el dos en esa lista aumenta mientras más números tenga la lista porque se hace más improbable que después de generar más números siga sin salir el número 2. De hecho, la probabilidad en este caso es 1 - (1/4)^n donde n es el número de números que tendrá la lista
La segunda probabilidad de la que hablas es cuando tienes una lista ya de números aleatorios enteros entre 0 y 3 y estás calculando la probabilidad de que al sacar cualquier número ese número que sacaste sea igual a 2. En este caso la probabilidad sería de aproximadamente 1/4. Fíjate que la probabilidad en este caso no depende de la longitud de la lista porque al ser números aleatorios saldrán más o menos con la misma frecuencia cualquiera de los cuatro números entre 0 y 3.
En caso de que estuvieras seguro que en una lista de n elementos el número que buscas sólo está una vez, la probabilidad de que al sacar un elemento ese sea el que buscas sí sería de 1/n, y por tanto disminuiría la probabilidad conforme crece la cantidad de elementos.
¡Hazme saber si te queda alguna duda! ;)
Si, pues en este caso los números aleatorios se pueden repetir. Entonces, entre mas cantidad de números haya, es más posible que se puedan repetir ciertos números.
Qué diferencia hay en una búsqueda lineal y una búsqueda binaria, donde en la ultima se indica que siempre se busca en la mitad de la lista para acortar el tiempo de búsqueda?
¡Hola @maxdatha! Te comento, una búsqueda lineal recorre todos los elementos de un array para encontrar un elementos en especifico, mientras que la busque binaria (que solo se puede realizar con array ordenados) se hace por mitades, es decir voy al elemento del medio del array y me fijo si ese elemento es mayor o menor al que estoy buscando, de ser mayor me quedo con la mitad las grande del array y hago el mismo ejercicio sobre el array reducido.
gracias por sus aportes
Alguien más tuvo que escribir import random al principio del código? No me reconocía random al principio
como norma general cuando se invoca un modulo tenemos que importarlo de la libreria.
Tambien se puede hacer ese ejemplo con un while y la propiedad iter() y next(). Algo asi:
falg = true values = iter(dic) while flag: if obj == next(values): flag = false
Genial Anthony, con iteradores.
Es un algoritmo de complejodad Lineal O(n). Por lo que su peor, PEOR, caso seria lim n=∞
Daniel Aroesti: define que tipo de clase de big o notation es Yo en la clase titulada Búsqueda lineal: no lo c tu dime XD
Hola, me surge una duda: ¿Como es que Python genera números aleatorios y qué complejidad tiene este método?
Hola, @josueNoha. :D
En Python existe un módulo llamado random que tiene muchos métodos para generar aleatoriedad en tus programas. Lo invocas así:
import random
En su documentación puedes conocer más del módulo random.
Por cierto el Libro tiene código en python!!!
¿Por qué David escribe el orden de las cosas que va a ejecutar en el mismo main y no utilizó una función como run()? ¿O es que run() no es fundamental?
¿run()? ¿De qué lenguaje vienes?
Es solo una manera de hacerlo. Si se utilizara run(), en su definición irían todos los comandos que David puso después de main.
¡Éxitos!
La parte de encontrado = búsqueda_lineal(lista, objetivo), me podrían explicar como funciona, se supone que la función inicia en falso y si lo encuentran pasa a verdadero y si no se queda en falso, pero al momento de imprimir la respuesta como es un if se asume que el fi siempre traera lo verdadero o como funciona esa parte?
import random def busqueda_lineal(lista, objetivo): match = False for elemento in lista: if elemento == objetivo: match = True return match if __name__ == "__main__": tamano_de_la_lista = int(input('De que tamaño sera la lista? ')) objetivo = int(input('Que número quieres encontrar ')) lista = [random.randint(0, 100) for i in range(tamano_de_la_lista)] encontrado = busqueda_lineal(lista, objetivo) print(lista) print(f'El elemento {objetivo} {"esta" if encontrado else "no estas"} en la lista')
No se si entendí bien tu pregunta. Pero estas en lo cierto en la asignación de match, se inicializa como false para evitar un else, además de que necesita estar inicializada con un valor default ya que será el valor retornado.
Y si te refieres al último print, los inline if funcionan así
"expression_if_true" if condition else "expression_if_false"
Hola! dentro de los corchetes, en el if, lo precede el string a pintar, si se cumple la condición, después el else precede al string que mostraras en caso de que no se cumpla, es así porque de alguna manera es declarativo, ya que literal es decir "pinto esto SI se cumple, SINO pinto esto otro".
En el ejemplo el docente coloca un operador ternario con un** if** y else, se puede realizar lo mismo incluyendo un elif? y como se haría?, traté de hacer un ejemplo con el elif y me arrojó invalid syntax. Gracias, quedo atento.
Hola @danielguarin07.
Me podrías decir en que minuto pone un else el profesor y también podrías compartir tu código del ejemplo que trataste hacer con elif para poder ayudarte a encontrar el error de syntax.
Saludos.
@crisTem lo puedes ver en la linea 21 en el minuto 6, posteriormente estará en la linea 22, el no lo menciona directamente , solo lo hace. Respecto al ejemplo, fue uno que no guardé, pero mas que todo es ver o saber si realmente se puede
Código
Ejecución
