No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

B煤squeda lineal

6/16
Recursos

Aportes 151

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 鈥榬andom鈥 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')

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. 馃槈

Notaci贸n 鈥淏ig O鈥 para varias operaciones en Python: https://wiki.python.org/moin/TimeComplexity

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:

鈥淎鈥 if True else 鈥淏鈥
鈥楢鈥

鈥淎鈥 if False else 鈥淏鈥
'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 鈥渕oderna鈥:

class c:
def f(self, arg = None):
self.arg = 42 if arg is None else arg
驴La ventaja? 隆Se lee de corrido! 鈥渟elf.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

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

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=鈭

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

PYHTON

LUA

ERLANG

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

B煤squeda lineal.

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

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

No s茅 que disfruto m谩s: las clases en s铆 o la investigaci贸n de las mismas.

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

馃(鈺枖鐨库枖)鈺疢i 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鈥 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>

pues no lo dice con el nombre del tema que es una funci贸n lineal == O(n) Lineal: la complejidad crecer谩 de forma proporcional a medida que crezca el input.


.
Este codigo es un ejemplo de busqueda lineal(Notacion Lineal). Aqui la complejidad del algoritmo depende de que tan grande sea la lista, la cual lo va a decidir el usuario. Primero por cada elemento de la lista va a checar si el elemento actual es igual al objectivo, si es asi match sera true. Despues en un for ternario, se creara una lista del tama帽o de la lista que el usuario eligio, y por cada elemento de este lista se creara un numero aleatorio. Entonces asi es como tenemos n numeros aleatorios. Entonces validamos esta ultima lista con el algoritmo que describi al principio para encontrar un objectivo en n numeros aleatorios.
.
Aqui la lista es nuestra n, el algoritmo sera tan complejo como grande sea la lista. Lo que encaja perfectamente con esta notacion O(n)
.

RESUMEN: La busqueda lineal es un ejemplo de un algoritmo de complejidad lineal, el cual va a ser tan grande como n se acerque al infinito

Al hacer el calculo de la busqueda del big O de este algoritmo olvide que se despreciaba lo pequeno y solo se consideraba lo mas grande, por lo cual considere todo input y output a lo largo del proceso. Aun asi llegue a algo como 鈥淥(n) + O(m)鈥 (habiendo llegado a la expresion mas pequena), por lo cual de todas formas seria lineal. Supongo que lo hice de una forma menos eficiente, pero me pregunto si habra casos en el que al considerar el panorama completo me dara algo distinto que al considerar solo el valor mas grande. Eso, Saludos 馃槂

import random

def busqueda_lineal(lista, objetivo):
    match = False
    for i in lista:         #O(n)
        if i == objetivo:
            match = True

    return match

if __name__ == "__main__":
    n = int(input("De que tama帽o quieres tu lista: "))
    lista = [random.randint(1, 100) for _ in range(n)]
    objetivo = int(input("Que n煤mero quieres encontrar: "))
    #print(lista)
    #print(objetivo)
    if busqueda_lineal(lista, objetivo):
        print(f"El n煤mero {objetivo} esta en la lista")
    else:
        print(f"El n煤mero {objetivo} no esta en la lista")
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__':
    tama帽o_de_lista = int(input("De que tama帽o sera la lista?"))
    objetivo = int(input("Que numero quieres encontrar?"))

    lista = [random.randint(0, 100) for i in range(tama帽o_de_lista)]
# operadores ternarios : genera if else en una sola linea

    encontrado = busqueda_lineal(lista, objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')

A mi me da O(2n+8) = O(n)

Buenas tardes, jovenes!

No me quer铆a quedar con la duda de como se ver铆a con la lista ordenada y solo agregue una linea para poder cumplir el objetivo. Les comparto el c贸digo final:

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?\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)

    lista_ordenada = sorted(lista)

    print(f'Lista original: {lista}\n')
    print(f'Lista ordenada: {lista_ordenada}\n')

    print(f'El numero {objetivo} {"esta" if encontrado else "no esta"} en la lista')

Espero les sirva y #HappyCoding!

Grandiosa clase 馃槃.

Algoritmo de B煤squeda Lineal

  • El algoritmo de b煤squeda lineal es un algoritmo simple, donde cada elemento de la lista (empezando por el primer elemento) es investigado hasta que es encontrado el elemento requerido, o se ha alcanzado el final de la lista.

  • El algoritmo de b煤squeda lineal es implementado en Python de la siguiente manera

def linearSearch(item,my_list):
found = False
position = 0
while position < len(my_list) and not found:
if my_list[position] == item:
found = True
position = position + 1
return found

  • Vamos a probar el c贸digo. Introduce la sentencia al final del script de Python de arriba
bag = ['book','pencil','pen','note book','sharpener','rubber']
item = input('What item do you want to check for in the bag?')
itemFound = linearSearch(item,bag)
if itemFound:
    print 'Yes, the item is in the bag'
else:
    print 'Oops, your item seems not to be in the bag'
  • Vamos a probar el c贸digo. Introduce la sentencia al final del script de Python de arriba

Hola, otro ejemplo de operardor ternario:
Como lo har铆amos normalmente:

age = 19
if age >= 18: 
	print(f"Mayor de edad {age}")
else: 
 	print(f"Menor de edad {age}")

Con operador ternario:

print(f"Mayor de edad {(age)}") if age >= 18 else print(f"Menor de edad {age}") 

Hola, que tal! Por si quieres profundizar en los operadores ternarios:
https://www.youtube.com/watch?v=3Xz9GqS46CI

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 鈥淥ptimizacion 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?

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.

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!!馃榿

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)

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

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