Búsqueda lineal

Si a alguien le aparece el siguiente error
NameError: name ‘random’ is not defined
coloquen lo siguiente al inicio del código
import random
😃

Wowwww, no sabia lo de poner el if en la cadena. Python es lo mejor.

https://github.com/karlbehrensg/poo-y-algoritmos-python

Búsqueda lineal

La búsqueda lineal es un algoritmo muy sencillo. Consta en buscar si un elemento se encuentra dentro de una lista, array o un sistema ordenado o no ordenado para poder determinar si el elemento se encuentra en el o forma parte de el.

¿Cuál es el peor caso del siguiente código? Si nos fijamos existe un for loop que crece según el tamaño de la lista, por lo cual nuestro Big O es O(n).

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_de_lista = int(input('De que tamano sera la lista? '))
    objetivo = int(input('Que numero 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')

Notación “Big O” para varias operaciones en Python: https://wiki.python.org/moin/TimeComplexity

Intente ver que sucedía se si hacia más grande la lista y el rango de números aleatorios.

Lo que me pareció sorprendente fue al abrir top en mi terminal…

Ese programa que parecía tan simple colapso mi sistema, cuando %MEM llega al 87% ya no podía hacer nada y no tenia opción debía desconectar mi Laptop (tengo 8GB de RAM).
Me parece fascinante lo que puede llegar hacer un simple proceso de calculo cuando su input aumenta. En este caso a mayor entrada de input, mayor su consumo de recursos. 😉

Como puedo saber la complejidad algoritmica si reemplazo por esta función?

def busqueda_lineal(lista, objetivo):
    return objetivo in lista

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 ')

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”

Notas de al sesión 😄
Búsqueda lineal.

• Una habilidad importante de un computer scientist es reducir cualquier problema a otros que ya sabemos resolver.
• La búsqueda lineal es sencilla, ya que busca en todos los elementos de manera secuencial.
• El peor caso es que el elemento se encuentre al final, por lo tanto tenemos $O(n)$.
• Podemos generar un 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")) 	

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;
}

Complejidad de las funciones nativas de python documentación oficial
TimeComplexity

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

Alguien más tuvo que escribir import random al principio del código? No me reconocía random al principio

Es un algoritmo de complejodad Lineal O(n). Por lo que su peor, PEOR, caso seria lim n=∞

Dentro de nuestra complejidad algoritmica, es importante tener en cuenta que el break, solo daría un mejor resultado en un caso promedio.

La búsqueda lineal es un algoritmo muy sencillo. Consta en buscar si un elemento se encuentra dentro de una lista, array o un sistema ordenado o no ordenado para poder determinar si el elemento se encuentra en el o forma parte de el.

¿Cuál es el peor caso del siguiente código? Si nos fijamos existe un for loop que crece según el tamaño de la lista, por lo cual nuestro Big O es O(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

🦾(╬▔皿▔)╯Mi aporte, agregue un try para mostrar tanto el numero objetivo que estamos buscando como la posición en que se encuentra.
el except maneja el error en caso de no encontrarlo.

import random # Importa la libreria random para usar la funcion randint


def busqueda_lineal(lista, objetivo):
    match = False

    for elemento in lista:# O(n) Es una busqueda lineal.
        if elemento == objetivo:
            match = True
            break # Una vez que encuentra el objetivo se detiene.

    return match


def main():
    list_size = int(input('¿Qué tamaño tendra la lista?:\n'))
    objetivo = int(input('¿Qué número quieres encontrar?:\n'))

    lista = [random.randint(0,100)for i in range(list_size)] # Genera lista aleatoria de numeros enteros de tamaño list_size

    encontrado = busqueda_lineal(lista, objetivo) # Ejecuta la funcion busqueda_lineal
    print(f'{"═" * 80}\n')# Imprime 80 caracteres para separacion.
    print(lista,'\n')
    try:# Evalua si existe el numero dentro de la lista y lo imprime junto con su pocision.
        print(f'{"═" * 80}\n')
        print(f'El número {objetivo} esta en la posición {lista.index(objetivo)}\n')
    except ValueError:# Muestra mensaje en caso de no encontrarlo.
        print(f'{"═" * 80}\n')
        print(f'El número {objetivo} no esta en la lista\n')
        print(f'{"═" * 80}\n')



if __name__ == '__main__':
    main()

Hola a todos, hice un miniprograma aplicando lo que aprendi aqui, la complejidad de mi algoritmo es O(n). Este es el codigo:

<word = input('please introduce a word: ') #complejidad O(n)
found = False
while found == False:
    letter = input('now write a letter: ')
    print(f'{"congrats letter is in word" if letter in word else "sorry, letter not in worrd try again"}')
    if letter in word:
        break>

Mi implementacion.

agregando sorted al inicio logro ordenar la lista
lista =** sorted**([random.randint(0, 100) for i in range(tamaño_de_lista)])

Muy interesante la clase y muy practico el tema de los operadores ternarios

Complejidad de la busqueda lineal = O(n)

es un algoritmo O(n), ya que es un solo loop…o asi entendi de la anterior clase. y por ese motivo tambien es busqueda lineal dato por dato

Vaya! esto si lo entendi!

Código

Ejecución

Búsqueda Lineal
Busca la coincidencia en todos los elementos de manera secuencial (1 a 1).
Su complejidad es lineal O(n)
Notas

• Recordemos que para resolver un problema grande lo dividimos en problemas pequeños cuya solución ya conozcamos.
• Operadores ternarios en python (if en una sola línea de código):
  <expresion1>if<condicion>else<expresion2>

Si tengo una lista de 100 elementos y voy buscando uno por uno, el peor caso es que sea el útlimo, yo diría que O(n)

Comparto mi codigo con algo menos de lineas en la funcion y una forma mas optimizada de importar un modulo

from random import randint

def busqueda_lineal(lista, objetivo):
    for elemento in lista:
        if elemento == objetivo:
            return True
    
    return False


if __name__ == '__main__':
    tamano_lista = int(input('De que tamaño sera la lista? '))
    objetivo = int(input('Que numero deseas encontrar? '))
    
    lista = [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')

Podemos comparar uno a uno los elementos de la lista con el valor de x, y retornar el valor de la posición donde lo encontramos en caso de encontrarlo.

Si llegamos al final de la lista sin haber salido antes de la función es porque el valor de x no está en la lista, y en ese caso retornamos −1.

En esta solución necesitamos una variable i que cuente en cada momento en qué posición de la lista estamos parados. Esta variable se inicializa en 0 antes de entrar en el ciclo y se incrementa en 1 en cada paso.

def busqueda_lineal(lista, x):
    """ Búsqueda lineal.
    Si x está en lista devuelve su posición en lista, de lo
    contrario devuelve -1.
    """

# Estrategia: se recorren uno a uno los elementos de la lista
# y se los compara con el valor x buscado.
i=0 # i tiene la posición actual en la lista, comienza en 0

# el ciclo for recorre todos los elementos de lista:
for z in lista:
    # estamos en la posicion i, z contiene el valor de lista[i]

    # si z es igual a x, devuelve i
    if z == x:
        return i

    # si z es distinto de x, incrementa i, y continúa el ciclo
    i=i+1

# si salió del ciclo sin haber encontrado el valor, devuelve -1
return -1

Y ahora lo probamos:

>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 44)
-1
>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 3)
3
>>> busqueda_lineal([1, 4, 54, 3, 0, -1], 0)
4
>>> busqueda_lineal([], 0)
-1

Dejo un pequeño programa de complejidad O(n)

Ejercicio
Escribir un programa que le diga al usuario que ingrese una cadena.
El programa tiene que evaluar la cadena y decir cuántas letras mayúsculas tiene.
Un detalle para novatas como yo, es que tuve que descartar los espacios vacíos, ya que el intérprete los tomaba como mayúsculas y sumaba al contador.

def contando_mayusculas(cadena):
    contador=0
    for i in cadena:
        if i == i.capitalize() and i != ' ':
            contador+=1


    print('Tu input contiene ',contador,' mayúsculas')

if __name__ == '__main__':

    cadena = input('Ingresá una palabra o frase, usando mayúsculas y minúsculas mezcladas: ')
    
    contando_mayusculas(cadena)

My code.

#PHASE 1. crear lista automaticamente, el usuario decide la longitud y el sistema completa la lista con numeros aleatorios en cierto rango especificado.
#PHASE 2. preguntar al user un numero e informar si el escrito se encuentra en la lista generada de forma aleatoria.

import random

def match_num_in_list(objetivo, the_list):

    encontrado = False

    for numero in the_list:
        if numero == objetivo:
            encontrado = True
            break
    return encontrado

def create_ramdom_list(amount):

    this_list = [random.randint(1,100) for i in range(amount)]
    return this_list

if __name__ == "__main__":
    
    list_amount = int(input("Tamaño de la lista: "))
    guess_number = int(input("Numero a buscar: "))

    print(f'El numero: {guess_number}, {"esta" if match_num_in_list(guess_number, create_ramdom_list(list_amount)) else "no esta"} en la lista')

running

Excelente curso, aprendiendo mucho

Para nuestro algoritmo de búsqueda lineal ¿Cuál sería el peor caso?

Resumen: Búsqueda lineal

F = O(1) + O(x) + O(x) = O(1) + 2O(x) ~ 2O(x) ~ O(x)

F = O(x) es una función lineal.

Los operadores ternarios, son lo que pueden generar statements, en una sola líena de código.

El entry point, es bien necesario, debido a que define varias cosas: primera de ellas, es el comienzo de ejecución, es decir, dónde tendremos nuestro inicio del script, en caso de que ese archivo en específico se ejecute directamente. Segundo: Porque podemos necesitar importar algo del archivo. Si queremos traer orden a nuestro código, vamos a necesitar definir, en dónde tendremos el código reutilizable, y en dónde llamamos ese código reutilizable. Por lo que en pocas palabras, necesitamos un entry point.

La búsqueda lineal, es sencilla. Solo tenemos que recorrer un arreglo (ordenado o no), tratando de encontrar un elemento.

Entender, cómo dar solución a nuestros problemas, con algoritmos conocidos, o basados en estos, es una habilidad que requiere un computer scientist.

Como computer scientist, tienes que entender la computación, y las divergencias que surgen apartir de todos los conceptos, básicos. Sin embargo, es desde los conocimientos más básicos, que podemos solucionar problemas más complejos.

¿Y si hago esto?

tamaño_de_la_lista = int(input('tamaño de la lista:'))
    objetivo = int(input('que numero quieres encontrar? '))
    
    lista = [ random.randint(0, 100) for i in range(tamaño_de_la_lista) ]
    
    if objetivo in lista:
        print(f"El elemento {objetivo} esta en la lista")
    else:
        print('El elemento no esta en la lista')

El algoritmo de búsqueda lineal busca un elemento en un array empezando por el primer elemento hasta dar con el valor deseado.

Otra forma de escribir el código un poco más simple, aprovechando las utilidades que posee Python.
.

import random


def linear_search(random_list, objective):
    return objective in random_list


def run():
    list_size = int(input("What will be the size of the random list?: "))
    objective = int(input("What number do you want to get?: "))

    random_list = [random.randint(0, 101) for i in range(list_size)]
    located = linear_search(random_list, objective)

    print(sorted(random_list))
    print(f"The number {objective} {'is' if located else 'is not'} on the list")


if __name__ == "__main__":
    run()

Grande Teacher, David Aroesti, de los mejores profesores a mi parecer.

Aquí dejo mi código. Incluyo un contador para registrar el número de ejecuciones…

import random

def busqueda_lineal(lista,objetivo,contador):
    for item in lista:
        contador+=1
        if objetivo==item:
            return (True, contador)
        continue
    return(False,contador)

if __name__=='__main__':
    tamano_lista = int(input('Ingrese por favor el tamaño de la lista: '))
    objetivo = int(input('Ingrese por favor el objetivo: '))
    lista = [random.randint(0,100) for i in range(0,tamano_lista)]

    encontrado = busqu![numero ejecuciones.jpg](https://static.platzi.com/media/user_upload/numero%20ejecuciones-febee86e-4ffc-4093-bf98-0fb9ea377f04.jpg)eda_lineal(lista,objetivo,contador=0)

    print(lista)
    print(f'El número {objetivo} {"si fue" if encontrado else "no fue"} encontrado')
    print(f'La ejecución se realizó {encontrado[1]} veces')

2 Cosas:

1. Para mi, el peor caso, es no encontrar el elemento y haber gastado todo el loop
2. Cuando pienso en la complejidad, lo primero que busco son ciclos, pues los ciclos tienen complejidad ~0(N). En este caso, es una busqueda por todos los elementos, por lo tanto, es O grande de N.

Esta es otra opciòn

Es interesante saber este tipo de cosas que realmente para los que no tengan mayor conocimiento pueden ser innecesarias pero resulta que al a final no es solamente escribir codigo y ya, sino encontrar la solucion mas factible al problema para la optimizacion de recursos tiempo y calidad del producto, piensen en esto como si alguna App que usen en su nueva actualizacion coloquen un mensaje de “Optimizacion de rendimiento”. Allio es donde realmente se aplica esto.

Este capítulo responde lo siguiente:
¿En qué consiste la búsqueda lineal?
¿Cuál es la relación de la búsqueda lineal y la complejidad algorítmica?

PYHTON

LUA

ERLANG

es matematico

Estoy tan feliz de haber acertado al final nejndxujsd

import random


def busqueda_lineal(lista, objetivo):
    match = False

    for elemento in lista: #loop depende de un input 0(n)
        if elemento == objetivo:
            match = True
            break
    
    return match

if __name__=="__main__":
    tamano_de_lista = int(input("¿De que tamaño sera la lista?: "))
    objetivo = int(input("¿Que numero quieres encontrar?: "))

    lista = [random.randint(0,10000) for i in range(tamano_de_lista)] #Generar una lista del tamaño de la lista, llena de numeros aleatorios

    encontrado = busqueda_lineal(lista,objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista') #Operadores ternarios, podemos genera un if else en una misma linea de codigo

Hola a todos, comparto con ustedes el código que realicé en Jupyter Notebook para esta clase. Notarán que hice una variación en el ciclo for para que elcódigo indique la posición del primer objetivo que encontró en la lista aleatoria. Saludos

Muy buena clase.

No sé que disfruto más: las clases en sí o la investigación de las mismas.

import random

def busqueda_lineal(lista, objetivo):
    match = False

    for elemento in lista:
        if elemento == objetivo:
            match = True
            break

    return match

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista?'))
    objetivo = int(input('que numero 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 ')

# ¿Por que me ocurre esto?
#  encontrado = busqueda_lineal(lista, objetivo)
#             ^
#SyntaxError: invalid syntax

Aquí un poco de información acerca de los operadores ternarios

O(n)

La complejidad algorítmica es de O(n)

Qué Bien!!! Vamos!!😁

El peor caso es que el valor buscado se encuentre al final de la lista 😦

Muy bien explicado!

Si no logras entender el codigo puedes usar esta version simplificada:

def linear_search(array, aim):
	match = False
	for i in range(0, len(array)):
		if i == aim:
			match = True
			return match
	else:
		return match

if linear_search(array = [1, 23, 43, 4, 5, 0, 634, 2 ,34, 12, 3, 4], aim = 0) == True:
	print("Element found in the given array!")
else:
	print("Element wasn't found in the given array")

Esta es la misma versión pero en vez de usar el array dado toma el input del usuario y lo convierte en una lista para que pueda ser manipulado (incluye comentarios):

#Program for writing a list of numbers, converting them to ints and finding a target
#Linear Search
#Array of numbers

#User is asked to input a series of numbers followed by "," ex: 1,2,3,4,5,6
values = input("Input some comma seprated numbers in which you want to find the target: ")
arr1 = values.split(",") #The values are splited by commas and there they are stored in an array list as strs
print(arr1)	#arr1 is printed to see our input

#our target is the number we wanna find in our list, and is converted into an int
target = int(input("What's the number you are searching for?: "))

#str_to_int(arr1) converts the arr1 string elements (that are in strs) into ints
def str_to_int(arr1):
	for i in range(0, len(arr1)):	#for every index in the range of 0 to the total length of the array
		arr1[i] = int(arr1[i])	#It will take that indexes of each values in the array and convert them into ints
		return arr1		#Returns the new value of arr1

#This is the linear search function. Recieves as argument the arr1 list and the target
def linear_search(int_arr1, target1):
	#Calls the str_to_int(arr1) function
	str_to_int(arr1)
	global i #i is defines as global to be able to be called at the end
	for i in range(0, len(arr1)):	#For the i in the range of the total length of the int_arr1 
		if i == target:	#Will compare if the i is a target
			return True	#If the above order is true, returns that the target was found
	else:	#If nothing is found
		return False #Returns false 

#If the linear_search found the target
if linear_search(int_arr1 = arr1, target1 = target) == True:
	print(f"{target} is in {i} position")	#It will print the position of the target
else:	#Otherwise = not found (False)
	print(f"{target} wasn't found")	#Print that the target wasn't found

Hola, una consulta. ¿Cuál es la tipografía que usa el profe en VS Code?

yo pensé que era O(log n)

Búsqueda lineal.

Peor de los casos O(n)
Mejor de los casos O(1)
Caso promedio O(n)

Alguien puede recomendar un libro para revisar a mayor profundidad sobre complejidad algorítmica?

Respondiendo a la pregunta que hizo el profesor cuál es el peor caso de una búsqueda Lineal ? Mi respuesta es:
El peor caso es que encontremos el valor en la última posición de una lista , o en último lugar.

Excelente.

Búsqueda lineal y examinación exhaustiva (del curso anterior) son lo mismo?

liinial

lineal

soy crack

la complejidad algoritmica es 0(n)

Lineal

me cuesta a ratos, pero creo que entendí el concepto

Busqueda lineal = crecimiento lineal

cuando ejecuto el código, siempre me arroja que el elemento no está en la lista

Vale!

Me toco buscar en una lista de mil, para que mi numero lo encontraran en la lista.
Si es un tema super interesante, poder revisar para cada algoritmo en que complejidad se mueve.

Otra manera de afrontar el problmea, solo que en este caso devolvemos el indice del item cuando lo encontramos o -1 si no lo encontramos.

# lineal or O(n)
def find_element_index_in_unsorted_list(list,element):
    """Given a list and an element from the list returns its position
    Parameters:
        list (list<?>): a sorted list of values
        element (?): whatever element existent in the list
    Returns:
        int: the position in the list or -1 if the item does not exist in the list"""
    index = 0

    while list[index] != element:
        index += 1
        
        if list[index] == element:
            return index
    
    return -1

import random

def busqueda_lineal(lista,  objetivo):
    match =False

    for elemento in lista:
        if elemento==objetivo:
            match=True
            break
        
    return match

if __name__ == "__main__":
    tamano_de_lista= int (input('De que tamano sera la lista \n'))
    objetivo = int(input('Que numero quieres encontrar \n'))

    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')

Busqueda Lineal

• Busca en todos los elementos de manera secuencial
• ¿Cual es el peor caso?

numeros random:

Usar librería random

random.ranint(0,100)

Funciones ternarias:

{<statement> if <condition> else <statement>}

import random

def busqueda_lineal(lista, objetivo):
    match = False

    for elemento in lista:
        if elemento == objetivo:
            match = True
            break
    
    return match

if __name__ == '__main__':
    tamano_de_lista = int(input('¿De que tamaño sera la lista? '))
    objetivo = int(input('¿Que numero desea 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')```

Esta línea no entiendo:
lista = [random.randint(0, 100) for i in range(tamano_de_lista)]

Interesante, esa es la razon por la cual implementar metodos de ordenamiento como el burbuja es ineficiente, dada necesidad de tener que recorrer todo el dataset en busqueda del valor.

Búsqueda lineal:

Si es un poquito confuso asimilar las clases con las operaciones, buscare mas información.

Sirmpre nos debemos fijar en el peor de los casos a la hora de analizar su complejidad algoritimica, como era un for que crecia a medida que la lista era grande entonces conclui que la complejidad es lineal O(n)

Ya voy aprendiendo a reconocer el tipo de complejidad de los algoritmos; este ejemplo fue muy ilustrativo. Gracias David.

import random

def linealSearch(list, obj):
	i = 0
	while i < len(list):
		if list[i] == obj:
			return i
		i += 1
	return -1

n = int(input("lenght list: "))
o = int(input("objective:   "))
l = [random.randint(0, 50) for i in range(n)]

finded = linealSearch(l, o)
print(l)
if finded != -1:
	print(str(o) + " is finded in posc " + str(finded))
else:
	print(str(o) + " is not finded")

Good class!!

si la lista es muy extensa, se vuelve ineficiente

Acá mi aporte que según lo que creo es un poco mas entendible

import random

def busqueda_lineal(lista, objetivo):
    ''' 
    O(n)

    int lista = []
    int objetivo
    match = False

    if objetivo in lista:
        match = True
    return match
    '''
    match = False

    for elemento in lista: # 0(n)
        if elemento == objetivo:
            match = True
            break
    
    return match


def main():
    tamano_lista = int(input('Tamano paraobjeto la lista: '))
    objetivo = int(input('Objetivo a encontrar: '))

    lista = [random.randint(0, 100) for i in range(tamano_lista)]

    busqueda_lineal(lista, objetivo)
    print(lista)

    if objetivo in lista:
        print(f'El elemento {objetivo} esta en la lista')
    else:
        print(f'El elemento {objetivo} no esta en la lista')
    
    #print(f'el elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')

if __name__ == '__main__':
    main()

Muy buena clase.

Algo importante para recalcar es que si queremos generar una lista con un tamaño por ejemplo de 100 con random.randint van a haber números repetidos lo cual en muchos casos no es lo que se busca. Una alternativa para generar una lista sin números que se repitan sería usar:

lista_numeros = list(range(100)) 
random.shuffle(lista_numeros)

Les dejo dos ejemplos del algoritmo de búsqueda lineal:

import random
import time

objective = int(input('enter an integer to search:'))
numbers = []
iteration = 0
start = time.time()
numbers = list(range(10)) 
random.shuffle(numbers)

for j in numbers:
    iteration += 1
    if j == objective:
        final = time.time()
        finaltime = final - start
        print(f'number {objective} found in {iteration} iterations in {finaltime} seconds')
        break
    elif objective not in numbers:
        print(f'number {objective} not found in generated list')
        break

final = time.time()
finaltime = final - start
print(iteration)
print(numbers)
print(finaltime)

Y el de la clase:

import random

def linear_search(list_size, objective):

    iteration = 0
    match = False
    numbers = list(range(list_size)) 
    random.shuffle(numbers)
    print(numbers)

    for j in numbers:
        iteration += 1
        if j == objective:
            match = True
            break
        
    return match and print(f'{iteration} iterations')

if __name__ == "__main__":

    list_size = int(input('enter the size of the list: '))
    objective = int(input('enter the number to search: '))
    search = linear_search(list_size, objective)
    print(f'The number {objective} {"is" if search else "is not"} on the list')

Hice este pequeño juego basado en la practica de esta clase

import random
import os
puntos = 0

def busquedaLineal(lista, objetivo):
    global puntos
    if objetivo in lista:
        os.system("cls")
        print(f"Se encontro el numero {objetivo} en la lista:")
        print(lista)
        puntos += 1
        print(f"su puntuacion es: {puntos}")
    else:
        os.system("cls")
        print(f"No encontramos el numero {objetivo} en la lista:")
        print(lista)
        print(f"su puntuacion sigue siendo {puntos}")
        print("intente con otro numero")


while True:
    lista1 = [random.randint(0, 20) for i in range(10)]
    try:
        os.system("cls")
        print("escribe un numero del 0 al 20")
        print("si tu numero se encuentra en la lista random ganas")
        n = input("")
        n = int(n)
        n_type = type(n)

        if n <= 20:
            busquedaLineal(lista1, n)
            print("desea volver a jugar? escriba SI o NO")
            condition = input("")

            if condition.lower() == "si":
                pass
            elif condition.lower() == "no":
                os.system("cls")
                print("graciaspor jugar")
                print(f"su puntuacion maxima fue {puntos}")
                break
            else:
                os.system("cls")
                print("no es una respuesta valida")
                break
        else:
            os.system("cls")
            print("no colocaste un valor valido para jugar")
            break
    except ValueError as e:
        os.system("clss")
        print("no colocaste un numero")
        break