No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

Búsqueda lineal

6/16
Recursos

Aportes 146

Preguntas 25

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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.

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

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

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

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

Código

Ejecución

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

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

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

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

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

Complejidad de la busqueda lineal = O(n)

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

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>

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

PYHTON

LUA

ERLANG

🦾(╬▔皿▔)╯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.


Super ya he aprendido mejor a identificar complex algorithm, quiere decir que el curso esta bueno.

Búsqueda lineal.

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

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

Vaya! esto si lo entendi!

Les comparto mi código y mis apuntes: ```python import random def busqueda_lineal(lista, objetivo): match = False for elemento in lista: #O(n) if elemento == objetivo: match = True break # no modifica la complejidad algoritmica pero en promedio nos tardariamos menos. # pero siempre hay que pensar en el peor escenario o no existe? # el brake no servira de nada. return match # generar pequenio programar para generar listas, y preguntar cual seria el objetivo if __name__ == '__main__': # para importar y que se pueda ejecutar directamente el codigo 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') # cual es su complejidad algoritmica. # La funcion crece en O(n), O de N. O lineal ```

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

Se que fue un algoritmo sencillo, pero fue genial haber acertado en el tipo de complejidad haha

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

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)

Le agregué al programa que nos regrese, en caso de que encuentre el elemento, la posición en donde lo encontró en el arreglo:

import random

def busqueda_lineal(lista,objetivo):
    match = False
    i=0

    for elemento in lista: #Complejidad O(n)
        if elemento == objetivo:
            match = True
            break
        i += 1
    return match,i


if __name__ == '__main__':
    tamanio_lista = int(input('De que tamaño sera la lista?: '))
    objetivo =  int(input('Introduzca el numero a buscar: '))

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

    encontrado = busqueda_lineal(lista,objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado[0] else "no esta"} en la lista')
    if encontrado[0]:
        print(f'Posicion: lista[{encontrado[1]}]')



liinial

lineal

Excelente.

O(n)

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

Adjunto el código de la clase:

import random


def lineal_search(search_list, objective):
    """
    apply lineal search in a list (search_list) to find the "objective".
    :return: bool
    """
    match = False
    for element in search_list:
        if element == objective:
            match = True
            break
    return match


if __name__ == '__main__':
    len_of_list = int(input('what is the len of the list?'))
    objective = int(input('which number do you want to find?'))
    search_list = [random.randint(0, 100) for i in range(len_of_list)]

    finded = lineal_search(search_list, objective)

    print(search_list)
    print(f'the element {objective} {"is" if finded else "is not"} in '
          f'the list')

Me rompe un poco la cabeza que ‘encontrado’ lo definas con la función de búsqueda lineal.
Creo que son mañas de computer scientists

es matematico

Esta es otra opciòn

La complejidad algorítmica es de O(n)

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

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

si la lista es muy extensa, se vuelve ineficiente

bueno tuve una pequeña odisea de 1 semana (jaja) por este programa, resulta que queria actualizar mi python porque no corría el programa… y termine actualizando mi sistema operativo (debian 10). En fin, si no te corre el script actualizate a python 3.7.

La otra es que se dejo sin responder cual era el peor caso para este algoritmo, y el peor de los casos es cuando el objeto a buscar se encuentre al final de la lista.

si no entienden operadores ternarios, pueden usar esto:

if linear_search(array = list1, target = target) == True:
	print("element was found")
	
	
else:
	print("element not found")

Saben por qué el codigo siempre me devuelve que el número no está? Versión 3.8, el codigo tal cual la clase

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

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

Busqueda lineal = crecimiento lineal

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

yo pensé que era O(log n)

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

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.

Genial lo de los operadores ternarios.

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

Good class!!

5:39 list comprehension

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

Muchos al igual que yo, se preguntaron si es probable que se repitan los números generados al azar.

La respuesta es sí mis compañeros; y tampoco hay un método específico para generar una lista sin repeticiones ( al menos en Python, si alguien conoce el método en otro lenguaje seria genial si lo puede compartir)

En esos casos, cuando queremos una lista sin duplicidad de los datos(números) vamos a tener que trabajarlo “manualmente” 😦

Una técnica es ir almacenando en una lista los números ya generados, y cada vez que generas uno nuevo verificas si ya estaba en esa lista, lo que significa que está repetido. En ese caso lo rechazas y pasas a obtener otro número random hasta que finalmente se encuentre uno que no esté repetido.
import random

def lista_sin_repeticiones(tamaño,limite):
    i = 0
    lista_sin_repeticiones = []
    for i in range(tamaño):
        numero_azar = random.randint(0,limite)
        while numero_azar in lista_sin_repeticiones: #!mientras que ese numero al azar ya se encuentre en la lista generada
            numero_azar = random.randint(0,limite)   #!...entonces genero otro numero
        else:
            lista_sin_repeticiones.append(numero_azar)
        i = i + 1
    return lista_sin_repeticiones

if __name__ == "__main__":
    tamaño_lista = int(input("Cuál es el tamaño de la lista? "))
    limite = int(input("Ingrese el limite para el rango de numeros generados al azar "))
    lista_con_repeticiones = [random.randint(0,limite) for i in range(tamaño_lista)]
    print(f'lista con repeticiones: {lista_con_repeticiones}')
    lista_final = lista_sin_repeticiones(tamaño_lista,limite)
    print(f'lista sin repeticiones: {lista_final}')

Tener en cuenta que tanto el range que se utilice para los elementos generados al azar como el lenght de la lista juegan un papel crucial para determinar si la solución es viable.

Como pueden observar en la última ejecución, entré en un loop infinito ya que mi límite para generar valores es desde 0 hasta 8 inclusive ==> [0,8] y 	estoy exigiendo que la lista sea de un lenght de 10; por lo tango nunca voy a llegar a obtener una lista final ya que utilicé todos los valores posibles (9 en total)


Espero que a alguien le sea útil 😃
Y si consideran que podria mejorarse el código o tienen otras técnicas por favor sean libres de compartir, todos estamos aprendiendo 😄
Saludos!


e aparece error de sintanxis en la palabra esta

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

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

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.

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

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.

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

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.

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

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

Qué Bien!!! Vamos!!😁

Lineal

la complejidad algoritmica es 0(n)

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

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

Búsqueda lineal:

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

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

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.

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

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.

Entendido

import random

def busqueda_lineal(lista, objetivo):
    match = False

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

    return match


def run():
    tamano_de_lista = int(input('Indique el tamaño de la lista:  '))
    objetivo = int(input('Que numero quiere buscar:  '))

    lista = [random.randint(0,100) for i in range(tamano_de_lista)]
    print(lista)
    encontrado = busqueda_lineal(lista, objetivo)
    print(f'El numero {objetivo} {"esta" if encontrado else "no esta"} en la lista.')

if __name__ == "__main__":
    run()

0(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_lista = int(input("Cual es el tamaño de la lista: "))
    objetivo = int(input("Cual el es numero a buscar? "))

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

    encontrado = busqueda_lineal(lista, objetivo)
    print(lista)
    print(f"El numero {objetivo}  {'Esta en la lista ' if encontrado else 'No esta en la lista'} ")```

Muy bien explicado!

Excelente clase…!

Muy buena clase.

Estoy tan feliz de haber acertado al final nejndxujsd

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?

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.

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