Búsqueda binaria

Wow se nota la efieciencia del codigo:

import random

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

    for elemento in lista:
        iter_lin+=1
        if elemento == objetivo:
            match = True
            break

    return (match,iter_lin)



def busqueda_binaria(lista, comienzo, final, objetivo,iter_bin=0):
    iter_bin+=1
    if comienzo > final:
        return (False,iter_bin)

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return (True,iter_bin)
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo,iter_bin=iter_bin)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo,iter_bin=iter_bin)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamaño es la lista? '))
    objetivo = int(input('¿Qué número quieres encontrar? '))

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

    (encontrado,iter_bin) = busqueda_binaria(lista, 0, len(lista), objetivo)
    (encontrado,iter_lin) = busqueda_lineal(lista, objetivo)

    #print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'Iteraciones busqueda lineal: {iter_lin}')
    print(f'Iteraciones busqueda binaria: {iter_bin}')

Complejidad Algorítmica utilizando el print statement.

El profesor en el minuto 12:04 dijo que cuando se trata de acceder mediante indices y venimos de un len le tenemos que restar 1.

Esto es porque len trabaja comenzando desde el 1-final, ya que cuenta los elementos, y nosotros como personas comenzamos a contar desde el 1 y no del cero

En cambio, los indices, trabajan desde el 0, por eso se le resta -1.

En los comentario les dejo un ejercicio para que se puede ilustrar mejor

• si tu lista esta ordenada, usar algoritmo de busqueda binaria
• si vas a utilizar muchas veces tu lista y no esta ordenada, es mejor ordenarla y utilizar algoritmo de busqueda binaria.
• si tu lista no esta ordenada y la vas a utilizar una sola vez, usar algoritmo de busqueda lineal.

Como dato curioso …
La búsqueda binaria tiene una complejidad de O( log n )

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

Búsqueda binaria

La búsqueda binaria toma una estrategia llamada “Divide y conquista”, la cual consiste en dividir el problema en 2 en cada iteración. Este algoritmo asume que la lista se encuentra ordenada, por lo que es necesario realizar este paso primero.

La búsqueda binaria es uno de los mejores algoritmos que se tienen hoy en día para búsqueda, ya que reduce significativamente el numero de pasos, y así disminuyendo nuestro Big O.

Para ver de forma practica haremos una búsqueda binaria a través de código. Lo primero que tenemos que realizar es ordenar nuestra lista antes de ejecutar la búsqueda.

import random

def busqueda_binaria(lista, comienzo, final, objetivo):
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)

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

Hola 😄, hice esta gráfica para comparar el número de iteraciones necesarias:

Si quieren ver el código para la gráfica, esta en este gist en GitHub.

aquí una buena explicación de por qué el algoritmo es logaritmico
https://riptutorial.com/es/algorithm/example/26648/o--log-n--tipos-de-algoritmos

Creo que lo correcto es decir que Objetivo > final, en lugar de comienzo > final, ya que esto lo aseguramos con la función sorted y no tiene sentido hacer ese if.

Siendo muy detallista
Yo intercambiaría el orden del if elif else para que haga la menor cantidad de comprobaciones porque el

if lista[medio] == objetivo:

es más probable que salte como falso cada vez hasta que lo encuentra. Me parece que esta forma estaría “mejor optimizado”

def busqueda_biseccion(lista,objetivo):

    mitad = len(lista) //2
    indice = mitad

    while indice >= 0 and indice <= len(lista) and mitad != 0:
        mitad //= 2
        print(mitad)
        if lista[indice] > objetivo:
            indice -= mitad
        elif lista[indice] < objetivo:
            indice += mitad
        elif lista[indice] == objetivo: 
            return True
            
    else:
            return False

Hice la solución para la búsqueda binaria y sí cuenta el número de iteraciones correctamente, pero marca un error (diría que es un warning, porque el programa sí corre). La implementación la adapté de esta fuente: stackoverflow Si alguien sabe por qué ocurre ese error o warning, lo agradecería.

Las pastillas de matrix de Morfeo
Tiempo vs Memoria

print statement es mi amigo, lo entendí a la perfección

Siempre y cuando la lista se pueda ordenar la búsqueda binaria siempre será la mejor opción, ya que completa la búsqueda en menor cantidad de iteraciones lo que la hace más eficiente.

import random

def busqueda_lineal(lista,objetivo):
    match = False
    iteracion_lineal = 0
    for elemento in lista:      
        iteracion_lineal +=1
        if elemento == objetivo:
            match = True
            break
    return (match,iteracion_lineal)

def busqueda_binaria (lista, comienzo, final, objetivo,iteracion_binaria):
    #print(f'Buscando {objetivo} entre {comienzo} y {final}')
    
    if comienzo > final:
        return False
    medio = (comienzo+final)//2
    iteracion_binaria += 1
    if lista[medio]== objetivo:
        return (True,iteracion_binaria)
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio+1, final, objetivo,iteracion_binaria=iteracion_binaria)
    else:
        return busqueda_binaria(lista, comienzo, medio-1, objetivo,iteracion_binaria=iteracion_binaria)
        

if __name__  ==   '__main__':

    tamano_de_lista = int(input('De que tamano sera la lista?'))
    objetivo = int(input('Que numero quieras encontrar?'))

    lista = sorted([random.randint(0,100) for i in range(tamano_de_lista)])
    
    encontrado_lineal = busqueda_lineal(lista, objetivo)
    encontrado_binario = busqueda_binaria(lista, 0, len(lista),objetivo,1)

    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado_lineal[0] else "no esta"} en la lista')
    print(f'El elemento {objetivo} {"esta" if encontrado_binario[0] else "no esta"} en la lista')
    print(f'Iteraciones Busqueda Lineal: {encontrado_lineal[1]}')
    print(f'Iteraciones Busqueda Binaria: {encontrado_binario[1]}')

"""
Salida

De que tamano sera la lista?67
Que numero quieras encontrar?98
[0, 7, 11, 11, 14, 16, 17, 18, 18, 19, 19, 20, 20, 22, 23, 25, 26, 27, 29, 31, 33, 34, 37, 41, 41, 41, 41, 44, 44, 45, 46, 46, 49, 51, 51, 54, 56, 58, 59, 63, 64, 65, 65, 66, 66, 68, 68, 75, 76, 76, 78, 78, 79, 80, 82, 82, 83, 83, 84, 87, 89, 89, 90, 93, 93, 98, 100]
El elemento 98 esta en la lista
El elemento 98 esta en la lista
Iteraciones Busqueda Lineal: 66
Iteraciones Busqueda Binaria: 6
 """

Reto con busqueda binaria

import random
import time

contador = 0 

def busqueda_binaria(lista, comienzo, final, objetivo):
    global contador
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2
    print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if lista[medio] == objetivo:
        contador = contador + 1
        return True

    elif lista[medio] <= objetivo:
        contador = contador + 1
        return busqueda_binaria(lista, medio +1, final, objetivo)

    elif lista[medio] >= objetivo:
        contador = contador + 1
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


if __name__ == "__main__":

    tamano_de_lista = int(input('De que tamano sera la lista? : '))
    objetivo = int(input('que numero quieres encontrar? : '))

    contador = 0
    lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)])
    
    inicio = time.time()
    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    final = time.time()

    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'La cantidad de pasos son: {contador + 1}')
    print(f'Se encontró en un tiempo de {(final - inicio)} ')```

buenos dias, dejo por aqui mi aporte

busqueda lineal:

import random
import time
pasos = 0
def busqueda_lineal(lista, objetivo):
    match = False
    global pasos
    for elemento in lista:
        if elemento == objetivo:
            match = True
            break
        pasos += 1
    return match

if __name__ == "__main__":
    tamano_de_lista = int(input("de que tamaño sera la lista? "))
    objetivo = int(input("que numero quieres encontrar?"))
    comienzo = time.time()

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

    encontrado= busqueda_lineal(lista, objetivo)
    print(lista)
    print("el elemento", objetivo, "esta" if encontrado else "no esta", "en la lista")
    final=time.time()
    print("tiempo de busqueda",final-comienzo)
    print("cantidad de pasos", pasos) 

y por aqui de busqueda binaria:

import random
import time

pasos=0

def busqueda_binaria(lista, comienzo, final, objetivo):
    print("buscando ", objetivo, "entre", lista[comienzo], "y" , lista[final-1] )
    
    global pasos

    if comienzo > final:
        pasos += 1
        return False

    medio=(comienzo + final) // 2
    pasos += 1

    if lista[medio] == objetivo:
        pasos += 1
        return True

    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)

    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)

    
if __name__ == "__main__":
    tamano_de_lista = int(input("de que tamaño sera la lista? "))
    objetivo = int(input("que numero quieres encontrar?: "))
    comienzo = time.time()

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)

    print(lista)
    print("el elemento", objetivo, "esta" if encontrado else "no esta", "en la lista")
    final=time.time()
    print("tiempo de busqueda",final-comienzo)
    print("cantidad de pasos: ", pasos)

Por aca dejo la implementación de la busqueda binaria usando bucles:

def busqueda_binaria(lista, objetivo):
  """Realiza búsqueda binaria en una lista y 
  retorna el indice del elemento encontrado, 
  si no lo encuentra retorna -1"""
  
  min = 0
  max = len(lista) - 1
  
  if objetivo < lista[min] or objetivo > lista[max]:
    return -1
    
  while min <= max:
    medio = (min + max) // 2
    if lista[medio] == objetivo:
      return medio
    elif lista[medio] > objetivo:
      max = medio - 1
    else:
      min = medio + 1

  return -1

Hay que destacar que el algoritno anterior devuelve la primera coincidencia, y si la lista tiene numeros repetidos, no hay garantia de que este resultado sea la primera ocurrencia, para lograr esto podemos añadir el siguiente código:

if primera_ocurrencia == True: #nuevo parámetro
        while medio >= 1 and lista[medio - 1] == lista[medio]:
          medio -= 1

Quedando el algoritmo asi:

def busqueda_binaria(lista, objetivo, primera_ocurrencia=False):
  """Realiza búsqueda binaria en una lista y 
  retorna el indice del elemento encontrado, 
  si no lo encuentra retorna -1"""
  
  min = 0
  max = len(lista) - 1
  
  if objetivo < lista[min] or objetivo > lista[max]:
    return -1
    
  while min <= max:
    medio = (min + max) // 2
    if lista[medio] == objetivo:
      if primera_ocurrencia == True:
        while medio >= 1 and lista[medio - 1] == lista[medio]:
          medio -= 1
      return medio
    elif lista[medio] > objetivo:
      max = medio - 1
    else:
      min = medio + 1

  return -1

Me esta costando un monton entender esto… Sienrto como que la explicación no es del todo buena o no me atrae para seguir aprendiendo…
Pero capaz que sea yo-

resultados del reto

jhonftb3@JFTB:/mnt/c/Users/user/Documents/poo_algor_python$ /usr/bin/python3.9 /mnt/c/Users/user/Documents/poo_algor_python/busquedaBinaria/reto_busq_bina.py
De que tamano sera la lista? : 1000
que numero quieres encontrar? : 46
Buscando 46 entre 11 y 10000
Buscando 46 entre 11 y 5019
Buscando 46 entre 11 y 2518
Buscando 46 entre 11 y 1230
Buscando 46 entre 11 y 588
Buscando 46 entre 11 y 285
Buscando 46 entre 11 y 121
Buscando 46 entre 11 y 52
Buscando 46 entre 44 y 52
Buscando 46 entre 44 y 43
[11, 20, 43, 44, 52, 65, 72, 93, 102, 112, 114, 120, 121, 136, 144, 145, 148, 152, 162, 173, 180, 211, 222, 232, 242, 257, 274, 284, 285, 290, 298, 304, 315, 318, 321, 327, 368, 369, 388, 404, 414, 416, 427, 437, 446, 449, 452, 467, 469, 481, 495, 496, 506, 518, 529, 536, 538, 550, 588, 588, 597, 598, 598, 615, 621, 641, 656, 658, 682, 689, 695, 699, 706, 716, 752, 781, 801, 817, 819, 821, 822, 833, 852, 859, 859, 862, 866, 866, 880, 907, 907, 918, 921, 921, 923, 927, 933, 939, 944, 949, 953, 979, 989, 993, 998, 1001, 1009, 1023, 1036, 1041, 1065, 1068, 1070, 1110, 1133, 1147, 1148, 1159, 1178, 1184, 1192, 1220, 1230, 1230, 1243, 1244, 1268, 1277, 1277, 1290, 1325, 1326, 1329, 1335, 1337, 1341, 1354, 1358, 1366, 1384, 1385, 1395, 1430, 1431, 1436, 1464, 1468, 1479, 1483, 1495, 1498, 1505, 1510, 1529, 1541, 1561, 1565, 1575, 1578, 1602, 1609, 1617, 1624, 1630, 1649, 1649, 1653, 1669, 1674, 1681, 1687, 1710, 1716, 1734, 1757, 1759, 1770, 1782, 1785, 1801, 1803, 1809, 1814, 1825, 1831, 1846, 1851, 1896, 1898, 1900, 1902, 1913, 1927, 1938, 2011, 2015, 2022, 2023, 2025, 2026, 2040, 2043, 2051, 2059, 2066, 2067, 2077, 2094, 2106, 2111, 2118, 2139, 2140, 2153, 2169, 2189, 2194, 2197, 2217, 2224, 2229, 2238, 2258, 2262, 2272, 2278, 2283, 2295, 2303, 2313, 2340, 2345, 2351, 2363, 2369, 2394, 2405, 2412, 2438, 2438, 2442, 2447, 2459, 2470, 2471, 2478, 2510, 2518, 2535, 2545, 2567, 2571, 2572, 2589, 2591, 2597, 2597, 2605, 2619, 2653, 2655, 2702, 2721, 2744, 2748, 2761, 2773, 2776, 2778, 2790, 2793, 2804, 2807, 2809, 2810, 2822, 2826, 2834, 2844, 2846, 2848, 2850, 2873, 2876, 2886, 2906, 2918, 2920, 2920, 2923, 2928, 2934, 2937, 2939, 2939, 2962, 2986, 3023, 3023, 3029, 3033, 3034, 3041, 3063, 3071, 3093, 3108, 3111, 3121, 3127, 3130, 3136, 3148, 3149, 3152, 3183, 3186, 3190, 3201, 3218, 3239, 3247, 3253, 3255, 3258, 3264, 3268, 3278, 3283, 3288, 3288, 3296, 3298, 3306, 3313, 3317, 3324, 3326, 3327, 3334, 3344, 3358, 3375, 3383, 3384, 3385, 3389, 3390, 3395, 3401, 3413, 3416, 3424, 3450, 3466, 3510, 3519, 3520, 3524, 3529, 3531, 3531, 3535, 3548, 3549, 3577, 3586, 3592, 3606, 3610, 3613, 3616, 3633, 3649, 3651, 3671, 3682, 3700, 3702, 3745, 3753, 3805, 3812, 3833, 3838, 3842, 3849, 3902, 3906, 3918, 3929, 3931, 3939, 3943, 3948, 3958, 3966, 3976, 3978, 4025, 4026, 4037, 4038, 4050, 4057, 4059, 4069, 4071, 4077, 4091, 4102, 4118, 4149, 4155, 4162, 4176, 4199, 4205, 4217, 4232, 4237, 4238, 4249, 4258, 4259, 4287, 4293, 4317, 4319, 4320, 4322, 4357, 4360, 4373, 4392, 4393, 4400, 4416, 4425, 4426, 4435, 4441, 4463, 4463, 4464, 4473, 4513, 4525, 4525, 4601, 4609, 4616, 4642, 4651, 4671, 4672, 4676, 4681, 4682, 4683, 4710, 4712, 4715, 4740, 4745, 4745, 4746, 4749, 4749, 4759, 4776, 4782, 4786, 4805, 4814, 4819, 4824, 4827, 4832, 4845, 4846, 4846, 4856, 4866, 4867, 4871, 4876, 4898, 4899, 4919, 4934, 4936, 4966, 4979, 4989, 5005, 5011, 5019, 5019, 5023, 5033, 5046, 5120, 5127, 5137, 5160, 5171, 5190, 5192, 5193, 5208, 5217, 5243, 5253, 5270, 5280, 5281, 5283, 5292, 5295, 5319, 5323, 5379, 5386, 5405, 5407, 5409, 5432, 5438, 5455, 5470, 5472, 5473, 5480, 5507, 5508, 5520, 5534, 5537, 5550, 5551, 5592, 5594, 5599, 5602, 5603, 5608, 5619, 5636, 5648, 5650, 5653, 5657, 5659, 5669, 5680, 5690, 5695, 5711, 5717, 5723, 5723, 5729, 5751, 5754, 5774, 5816, 5818, 5841, 5854, 5890, 5899, 5902, 5907, 5910, 5913, 5923, 5925, 5940, 5949, 5962, 5965, 5984, 5985, 5988, 6010, 6029, 6039, 6044, 6056, 6069, 6087, 6097, 6108, 6116, 6122, 6135, 6147, 6163, 6163, 6168, 6168, 6172, 6189, 6208, 6213, 6215, 6232, 6233, 6243, 6256, 6264, 6274, 6293, 6295, 6316, 6320, 6325, 6330, 6360, 6376, 6384, 6395, 6399, 6402, 6407, 6410, 6417, 6472, 6502, 6507, 6517, 6535, 6537, 6548, 6553, 6556, 6569, 6583, 6587, 6590, 6604, 6617, 6621, 6626, 6630, 6632, 6634, 6644, 6654, 6656, 6656, 6674, 6685, 6689, 6702, 6709, 6711, 6711, 6733, 6746, 6753, 6774, 6777, 6813, 6824, 6840, 6845, 6852, 6866, 6871, 6885, 6909, 6915, 6918, 6938, 6940, 6948, 6956, 6971, 6982, 6987, 6990, 6994, 7003, 7004, 7032, 7032, 7033, 7065, 7101, 7104, 7118, 7129, 7140, 7144, 7175, 7176, 7190, 7226, 7247, 7262, 7262, 7291, 7292, 7303, 7306, 7310, 7314, 7318, 7329, 7331, 7337, 7346, 7361, 7367, 7371, 7385, 7386, 7396, 7404, 7407, 7409, 7411, 7421, 7421, 7427, 7439, 7443, 7444, 7452, 7479, 7485, 7496, 7496, 7498, 7523, 7524, 7533, 7534, 7543, 7577, 7579, 7591, 7595, 7627, 7632, 7643, 7646, 7659, 7663, 7682, 7685, 7688, 7692, 7693, 7696, 7706, 7722, 7722, 7723, 7730, 7732, 7774, 7774, 7779, 7793, 7802, 7822, 7838, 7844, 7884, 7888, 7889, 7919, 7927, 7927, 7928, 7928, 7952, 7954, 7997, 8004, 8010, 8019, 8021, 8044, 8059, 8065, 8070, 8072, 8075, 8090, 8091, 8093, 8099, 8101, 8105, 8111, 8112, 8129, 8157, 8162, 8166, 8169, 8177, 8184, 8186, 8190, 8202, 8204, 8218, 8245, 8245, 8267, 8272, 8276, 8276, 8282, 8284, 8297, 8298, 8300, 8316, 8345, 8354, 8355, 8358, 8359, 8361, 8367, 8371, 8377, 8383, 8390, 8404, 8417, 8435, 8436, 8448, 8462, 8486, 8494, 8504, 8533, 8574, 8587, 8600, 8603, 8639, 8695, 8710, 8712, 8715, 8717, 8745, 8758, 8759, 8767, 8770, 8779, 8780, 8791, 8793, 8793, 8794, 8826, 8829, 8833, 8840, 8842, 8847, 8847, 8848, 8848, 8853, 8865, 8876, 8885, 8892, 8913, 8928, 8930, 8943, 8961, 8965, 8979, 8987, 8991, 9003, 9007, 9026, 9028, 9035, 9055, 9079, 9085, 9085, 9104, 9108, 9134, 9140, 9156, 9163, 9170, 9195, 9195, 9195, 9195, 9211, 9216, 9216, 9241, 9271, 9273, 9274, 9278, 9291, 9294, 9299, 9300, 9322, 9327, 9335, 9336, 9362, 9378, 9390, 9397, 9408, 9440, 9442, 9446, 9450, 9474, 9483, 9484, 9494, 9495, 9498, 9504, 9506, 9508, 9512, 9520, 9524, 9542, 9543, 9547, 9566, 9584, 9585, 9592, 9600, 9603, 9626, 9629, 9635, 9635, 9636, 9650, 9658, 9663, 9670, 9675, 9677, 9677, 9689, 9699, 9702, 9708, 9720, 9743, 9751, 9768, 9770, 9776, 9782, 9795, 9828, 9828, 9844, 9856, 9856, 9860, 9870, 9876, 9906, 9907, 9910, 9911, 9917, 9919, 9934, 9943, 9948, 9954, 9963, 9990, 10000]
El elemento 46 no esta en la lista
La cantidad de pasos son: 11
Se encontró en un tiempo de 0.00014972686767578125 

import random
import time

contador = 0 

def busqueda_binaria(lista, comienzo, final, objetivo):
    global contador
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2
    print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if lista[medio] == objetivo:
        contador = contador + 1
        return True

    elif lista[medio] <= objetivo:
        contador = contador + 1
        return busqueda_binaria(lista, medio +1, final, objetivo)

    elif lista[medio] >= objetivo:
        contador = contador + 1
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


if __name__ == "__main__":

    tamano_de_lista = int(input('De que tamano sera la lista? : '))
    objetivo = int(input('que numero quieres encontrar? : '))
    # el contador que se agrega 
    contador = 0
    lista = sorted([random.randint(0, 10000) for i in range(tamano_de_lista)])
    
    inicio = time.time()
    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    final = time.time()

    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'La cantidad de pasos son: {contador + 1}')
    print(f'Se encontró en un tiempo de {(final - inicio)} ')

Hay una gran diferencia en la medida que la lista de búsqueda es cada vez mayor

Yo veia que en ocasiones el rango de busqueda tenia el mismo inicio o el mismo fin, y el inicio o el fin tenian el objetivo, entonces tuve en cuenta validar tanto el inicio, el medio y el fin.

Tambien vi que en ocaciones el inicio o el fin se repetian varias veces, pero era innecesario tener en cuenta esos puntos porque ya los habia validado, entonces ya no los tenia en cuenta en la siguiente iteracion.

Que les parece ?

El debugger de Python se ha hecho de mis mejores herramientas. Incluso mejor que el print statement.

Creo que este algoritmo tiene un error

Me dí a la tarea de entender en mí cuaderno lo que el agoritmo hace para encontrar el número por búsqueda binaria. Me dí cuenta que cuando uno busca números pequeños, y por tanto, el medio es mayor al objetivo entonces el algoritmo debe correrse una posición a la izquierda para volver a interar en ese segmento de la lista (línea 15 del código del profe) (medio -1). En realidad no se corre una posición a la izquierda, se corre dos posiciones a la izquierda, dejando en cada ciclo un gap de una posición sin evaluar.

Este el código que copie de la clase, al cual le agregué varios prints statements para entender el proceso:

import random

def busqueda_binaria(lista, comienzo, final, objetivo):
    #Planeater el caso base:si el indice de comienzo es más grande que el final no se encontró el elemento
    print(f'buscando el {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    print(f'esta es la posición de inicio en la lista en este ciclo {comienzo} donde está el {lista[comienzo]}')
    print(f'esta es la posición final en la lista en este ciclo {final} donde está el {lista[final - 1]}')
    if comienzo > final:
        return False
    else:
        print(f'la posición del comienzo ({comienzo}) es menor a la posición del final ({final})')

    #Dividir la lista en dos    
    medio = (comienzo + final) // 2
    print(f' esta es la posición del medio: {medio} donde está el  {lista[medio]}') 
   

    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        busqueda_binaria(lista, comienzo, medio - 1, objetivo)
        

if __name__ == '__main__':

    tamano_lista = int(input('De qué tamaño es la lista?: '))
    objetivo = int(input('Qué número quieres encontrar?: '))

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"está" if encontrado else "no está"} en la lista')

Este es el primer ejercicio que hice. Primero está a salida en consola y luego mi análisis en el cuaderno:

Andres@DESKTOP-SH6T3IH MINGW64 /d/Documentos/PLATZI/Escuela_AI_ML/Curso_Python_POO (master)
$ py busqueda_bunaria.py
De qué tamaño es la lista?: 20
Qué número quieres encontrar?: 8
buscando el 8 entre 8 y 100
esta es la posición de inicio en la lista en este ciclo 0 donde está el 8
esta es la posición final en la lista en este ciclo 20 donde está el 100
la posición del comienzo (0) es menor a la posición del final (20)
 esta es la posición del medio: 10 donde está el  56
buscando el 8 entre 8 y 39
esta es la posición de inicio en la lista en este ciclo 0 donde está el 8
esta es la posición final en la lista en este ciclo 9 donde está el 39
la posición del comienzo (0) es menor a la posición del final (9)
 esta es la posición del medio: 4 donde está el  21
buscando el 8 entre 8 y 15
esta es la posición de inicio en la lista en este ciclo 0 donde está el 8
esta es la posición final en la lista en este ciclo 3 donde está el 15
la posición del comienzo (0) es menor a la posición del final (3)
 esta es la posición del medio: 1 donde está el  15
buscando el 8 entre 8 y 100
esta es la posición de inicio en la lista en este ciclo 0 donde está el 8
esta es la posición final en la lista en este ciclo 0 donde está el 100
la posición del comienzo (0) es menor a la posición del final (0)
 esta es la posición del medio: 0 donde está el  8
[8, 15, 15, 21, 21, 22, 27, 27, 39, 51, 56, 63, 64, 65, 73, 78, 88, 95, 98, 100]
El elemento 8 no está en la lista

En primer lugar nótese que yo estaba buscando el 8 que si está en la lista, pero no lo encontró

este es mi análisis en el cuaderno basado en los resultados en consola:
[](url https://drive.google.com/file/d/1yA_Bfn0ikzIRo8d3MIDTSFiGnPSaEw3A/view?usp=sharing)

Cada iteración se corre dos casillas a la izquierda (lineas azules muestran el gap que deja)

otro ejercicio:

$ py busqueda_bunaria.py
De qué tamaño es la lista?: 8
Qué número quieres encontrar?: 5
buscando el 5 entre 14 y 93
esta es la posición de inicio en la lista en este ciclo 0 donde está el 14
esta es la posición final en la lista en este ciclo 8 donde está el 93
la posición del comienzo (0) es menor a la posición del final (8)
 esta es la posición del medio: 4 donde está el  71
buscando el 5 entre 14 y 46
esta es la posición de inicio en la lista en este ciclo 0 donde está el 14
esta es la posición final en la lista en este ciclo 3 donde está el 46
la posición del comienzo (0) es menor a la posición del final (3)
 esta es la posición del medio: 1 donde está el  15
buscando el 5 entre 14 y 93
esta es la posición de inicio en la lista en este ciclo 0 donde está el 14
esta es la posición final en la lista en este ciclo 0 donde está el 93
la posición del comienzo (0) es menor a la posición del final (0)
 esta es la posición del medio: 0 donde está el  14
buscando el 5 entre 14 y 84
esta es la posición de inicio en la lista en este ciclo 0 donde está el 14
esta es la posición final en la lista en este ciclo -1 donde está el 84
[14, 15, 46, 48, 71, 82, 84, 93]
El elemento 5 no está en la lista 

el análisis en mi cuderno basado en consola que muestra que de nuevo el algoritmo se corre dos casillas a la izquierda y deja un gap:

y esto se esta dando creo que es porque en cada iteración está tomando la posició final tomando el primeri índice como 1 y no como 0 mientras que el medio si lo toma desde el primer indice contando desde 0 y no desde 1.

Me cuentan qué opinan, si estoy en lo correcto o si estoy malinterpretando los resultados o algun otro error!!

Estimados:

Para que el algoritmo funcione bien la llamada tiene que considerar el rango de índices de la lista, por lo que la llamada sería así:

encontrado = busqueda_binaria(lista, 0, len(lista) - 1, objetivo) 

y en el print se debe considerar_

print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final]}')

Si la llamada se hace desde len(lista), el elemento medio queda desfasado por uno más, y el algoritmo se “marea” en los últimos pasos. Acá un ejemplo (no es el mismo formato de print):

[10, 21, 26, 31, 33, 35, 37, 54, 75, 82] 

Se está buscando entre 10 y 82 - middle=35
Se está buscando entre 10 y 31 - middle=26
Se está buscando entre 31 y 31 - middle=31
Se está buscando entre 33 y 31 - middle=33 

Realizando la llamada hasta len(lista) - 1 (posición del último elemento de la lista, el algoritmo se comporta bien:

[2, 2, 3, 3, 6, 10, 12, 12, 13, 15, 16, 26, 28, 28, 29, 30, 34, 35, 39, 41, 42, 44, 45, 46, 49, 50, 50, 59, 65, 68, 69, 70, 72, 72, 73, 76, 78, 80, 82, 83, 86, 90, 94, 95, 95, 96, 97, 97, 99, 100]

Se está buscando entre 2 y 100 - middle=49
Se está buscando entre 2 y 46 - middle=26
Se está buscando entre 2 y 16 - middle=10
Se está buscando entre 2 y 6 - middle=3
Se está buscando entre 3 y 6 - middle=3
Se está buscando entre 6 y 6 - middle=6

El programa expuesto en la clase no “crashea” porque nunca usó el último elemento de la lista (excepto en el print, donde se agrega -1), ya que compara con el valor medio del rango. Sin embargo, si analizan los ejemplos, no coincide el comportamiento de la búsqueda bianaria con la operación teórica.

Me costó varias horas darme cuenta del problema 😕

se hubiese podido recortar la búsqueda comparando objetivo con inicio y final, ya que el 23 estuvo como final en 3 o 4 pasos

la secuencia debe estar ordenada de menor a mayor o también funciona si esta de mayor a menor?

Fijandome me he dado cuenta que cuando el profesor puso 100 como tamaño de la lista, le salieron los números del 1 al 100, lo cual es obvio por que el range es de 0 a 100. Pero me a generado inquietud el hecho de que en esa lista de 100 este el número 100 como tal, ¿no se supone que la función range(0, 100) no incluye al 100 en el rango numérico?

Aquí les dejo mi apunte de alguna manera, bueno yo lo entiendo haha, despues de los if, elif, else habia que especificar que son returns, bueno yo de esta manera veo mas fácil espero a alguien le sirva 😃

Aquí les dejo otra implementacion de la Busqueda Binaria:

def busq_binaria(lista,tamanio,objetivo):

    inicio = 0
    fin = tamanio-1
    mitad = (inicio + fin)//2

    while (mitad+1 != fin):

        mitad = (inicio + fin)//2

        if lista[mitad] == objetivo:
            return True
        
        if lista[mitad] < objetivo:
            ini = mitad
        else:
            fin = mitad

    return False

import random

#Tenemos un algoritmo O(log n) logaritmica
def busquedaBinaria(lista, inicio, final, objetivo, pasos):
    pasos = pasos + 1
    if inicio >= final:
        print(f'Se han ejecutado {pasos} pasos')
        return False

    print(f'Estamos buscando {objetivo} entre {lista[inicio]} y {lista[final - 1]}')
    medio = (inicio + final) // 2
    
    if lista[medio] == objetivo:
        print(f'Se han ejecutado {pasos} pasos')
        return True
    elif lista[medio] < objetivo:
        return busquedaBinaria(lista, medio+1, final, objetivo, pasos)                   
    else:
        return busquedaBinaria(lista, inicio, medio-1, objetivo, pasos)          
        
if __name__ == '__main__':
    tamanio = int(input('De que tamaño deseas la lista? '))
    objetivo = int(input('Cual es el numero que deseas encontrar? '))
    lista = sorted([random.randint(0,tamanio) for i in range(tamanio)])
    print(lista)
    encontrado = busquedaBinaria(lista, 0, len(lista), objetivo, 0)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')```

Tiempo por espacio, el gran dilema.

## Busqueda Binaria
## Asume que tenemos una lista ordenada
import random
import time

contador = 0

def BinarySearch(lista, start, end, objetivo):
    global contador

    if start > end:
        return False

    medio = (start + end) // 2
    
    if lista[medio] == objetivo:
        return True

    elif lista[medio] < objetivo:
        contador = contador + 1
        return BinarySearch(lista, medio + 1, end, objetivo)
    
    else:
        contador = contador + 1
        return BinarySearch(lista, start, end - 1, objetivo)
    
if __name__ == '__main__':
    size_list = int(input('What size is the list?'))
    objetivo = int(input('What number want you find? '))
    lista = sorted([random.randint(0, 100) for i in range(size_list)])

    start = time.time()
    finded = BinarySearch(lista, 0, len(lista), objetivo)
    end = time.time()

    print(f'El elemento {objetivo} {"esta" if finded else "Not found"} in the list')
    print(f'La cantidad de pasos son: {contador + 1}')
    print(f'El tiempo total es: ' + str((end - start))),

En busqueda lineal es valido usar este contador:

import random
def busqueda_lineal(lista, objetivo):
    match = False
    for elemento in lista: #0(n) o complejidad algoritmica lineal
        if elemento == objetivo:
            match = True
            break
        return match

def f(lista):
    contador = 0
    for i in lista:
        contador += 1
    return print(contador)


if __name__ == "__main__":
    tamano_de_lista = int(input("Escribe el tamaño de lista: "))
    objetivo = int(input("Que número 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 lista")
    f(lista)```

si hubieras escrito

lista[media] =< objetivo

no habria encontrado antes el 23?

Volviendo al comentario anterior, el print statement también tiene un error en su definición del indice final. Quedaría: lista[final].

Por otra parte, y tomando nuevamente como ejemplo test=[7, 24, 45, 76, 96] y objetivo 97; al tener el print statement antes de la validación:

    if comienzo > final:
        return False

También vamos a recibir un IndexError, ya que primero debemos validar que comienzo no se haya sobrepuesto a final antes de imprimir

Hola amigos, en los argumentos enviados a la función busqueda_binaria hay un error en el argumento final = len(lista), pues este genera un IndexError: list index out of range cuando estamos buscando un número mayor al número más grande dentro de nuestra lista, aquí un ejemplo:

Si tenemos la lista test=[7, 24, 45, 76, 96] y queremos buscar el 97, el algoritmo intentará seleccionar len(test) como indice final, lo que es igual a 5, pero 5 no es elemento válido dentro de test, ya que los elementos van desde 0 hasta 4; por ende final = len(test) - 1 para tomar el último elemento.

Espero les sirva… Saludos!

import random
import time
def busqueda_binaria(lista, inicio, final, objetivo):
    
   # print(f'buscando {objetivo} entre {lista[inicio]} y {lista[final - 1]}')

    mitad = (inicio + final) // 2

    if lista[mitad] == objetivo:
        return True
    elif lista[mitad] < objetivo:
        return busqueda_binaria(lista, mitad + 1, len(lista), objetivo)
    else:
        return busqueda_binaria(lista, inicio, mitad - 1, objetivo)

def busqueda_lineal(lista, objetivo):
    pasos = 0
    match = False
    for elemento in lista: # O(n)
        pasos +=1
        if elemento == objetivo:
            match = True
            break
        
    return match


if __name__ == '__main__':
    
    list_length = int(input('de qué tamaño es la lista? '))
    objetivo = int(input('qué número quieres encontrar? '))
    lista = sorted([random.randint(0, 1000)for i in range(list_length)])

    inicio_lineal = time.time()
    encontrado_lineal = busqueda_lineal(lista, objetivo)
    final_lineal = time.time()

    inicio_binario = time.time()
    encontrado_binario = busqueda_binaria(lista, 0, len(lista), objetivo)
    final_binario = time.time()

    tiempo_lineal = (final_lineal - inicio_lineal)
    tiempo_binario = (final_binario - inicio_binario)

    #print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado_lineal else "no esta"} en la lista, con búsqueda lineal')
    print(f'con este método se tardó {tiempo_lineal} de tiempo')
    print(f'El elemento {objetivo} {"esta" if encontrado_binario else "no esta"} en la lista, con búsqueda binaria')
    print(f'con este método se tardó {tiempo_binario} de tiempo')

Declare el contador como iteracion y se imprime el numero de iteracion en que va despues de cada busqueda

import random
def busqueda_binaria(iteracion, lista, comienzo, final, objetivo):

    while True:
        print(f'iteracion numero: {iteracion}')
        print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final-1]}')
        if comienzo > final:
            return False

        medio = (comienzo + final) // 2

        if lista[medio] == objetivo:
            iteracion = iteracion + 1
            return True

        elif lista[medio] < objetivo:
            iteracion = iteracion +1
            return busqueda_binaria(iteracion,lista, medio + 1, final, objetivo)

        else:
            iteracion = iteracion +1
            return busqueda_binaria(iteracion,lista, comienzo, medio -1, objetivo)


if __name__ == '__main__':
    tamano_lista = int(input('de que tamaño sera la lista? '))
    objetivo = int(input('que numero desea encontrar? '))
    iteracion = 0

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

    encontrado = busqueda_binaria(iteracion,lista, 0, len(lista), objetivo)
    print(lista)
    print(f'el elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')

Hola, Adjunto mi solución al reto.

import random

def busqueda_binaria(lista, comienzo, final, objetivo, counter):
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}') #se resta uno, debido al len. Recordar que se cuenta desde 0
    
    if comienzo > final:
        return respuesta

    medio = (comienzo + final) // 2 # Divison de enteros
    respuesta['counter'] = respuesta['counter'] + 1
   

    if lista[medio] == objetivo: #Encuentra el objetivo en el medio
        respuesta['validador'] = True
        return respuesta
    elif lista[medio] < objetivo: #Busca el objetivo en la parte superior
        return busqueda_binaria(lista, medio + 1, final, objetivo, respuesta)
    else: #Busca el objetivo en la parte inferior
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, respuesta)



if __name__ == '__main__':

    respuesta = {'counter': 0, 'validador': False}
    tamano_de_lista = int(input('De que tamano sera la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))
   
    lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)]) #Genera una lista del tamano de la lista con numeros aleatorios y ordena la lista
    
    respuesta = busqueda_binaria(lista, 0, len(lista), objetivo, respuesta)
    
    counter = respuesta['counter']
    validador = respuesta['validador']

    print(lista)
    print(f'El elemento {objetivo} {"esta" if validador else "no esta"} en la lista')
    print(f'El numero de pasos fue de {counter}')

Retorne dos valores en la función, esto lo retorna en forma de tupla, y necesita los parentesis, tengo entendido

import random

iterador = 0

def busqueda_binaria(lista, comienzo, final, objetivo, iterador):
    
    iterador += 1

    print(f'Buscando a {objetivo} entre {lista[comienzo]} y {lista[final-1]}')
    if(comienzo > final):
        return False
    
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo :
        
        return (True, iterador)
    elif lista[medio] < objetivo: 
        return busqueda_binaria(lista, medio + 1, final, objetivo, iterador)
    elif lista[medio] > objetivo:

        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, iterador)

if __name__ == "__main__":
    tamaño_lista = int(input('Tamaño de la lista: '))
    objetivo = int(input('Número a encontrar: '))

    lista = sorted([random.randint(0,100) for i in range(tamaño_lista)])

    encontrado, iteraciones = busqueda_binaria(lista, 0, len(lista), objetivo, 0)
    
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no está"} en la lista')
    print(f'Demoró {iteraciones} iteraciones')

Mi aporte al reto

<code>
import random

def busqueda_binaria(lista, comienzo, final, objetivo,iteraciones):
    iteraciones["total"]+= 1
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]} No iteraciones {iteraciones["total"]}')
    
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo,iteraciones)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo,iteraciones)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))
    iteraciones={"total":0}
    lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)])
    
    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo,iteraciones)

    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista, total ciclos: {iteraciones["total"]}')
</code>

El codigo dado en clase tiene un bug(error):

cuando estamos colocando {lista[final - 1]} en el siguiente print

print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}') ```



solo me esta mostrando bien la primera busqueda para que no quede fuera de rango pero estamos cometiendo un error porque en realidad el print no nos esta mostrando bien como esta iterando el sistema en cada busqueda, sobre todo cuando lista[medio] > objetivo, ya que cuando esto sucede la variable 'final' se vuelve
 final = medio - 1

return busqueda_binaria(lista, comienzo, medio - 1, objetivo)

entonces al hacer en el print  {lista[final - 1]}, estamos diciendole al sistema que a la variable final le reste 1 osea que estariamos haciendo esto:
final = medio - 1 - 1   , lo que ocasiona que el print se corra dos puestos y no muestre la verdadera iteracion.


he arreglado el codigo manejando el error con 'try', ya que toca colocar el print como {lista[final]}, pero si se dejara sin manejar el error, el sistema en la primera impresion saldria error y dejaria de funcionar porque estariamos por fuera de rango ya que final = len(lista), y ese indice no existiria que fue el motivo por el que el profesor resto 1, hizo {lista[final - 1]}, entonces el codigo correcto quedaria asi:

try:
print(f’Buscando {objetivo} entre {lista[comienzo]} y {lista[final]}’)
except IndexError:
print(f’buscando {objetivo} entre {lista[comienzo]} and {lista[final - 1]}’)
```

como pueden ver en el except coloque el mismo print y solo cambie la letra “y” por “and” para que cuando lo corran vea que esta funcionando es el print del except.

y aca va mi codigo completo:

import random

def busqueda_binaria(lista, comienzo, final, objetivo):

    if comienzo > final:
        return False

    try:
        print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final]}')
    except IndexError:
        print(f'buscando {objetivo} entre {lista[comienzo]} and {lista[final - 1]}')
    
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True

    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)

    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


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

    lista = sorted([random.randint(0, 100) for i in range(tamaño_de_lista)])

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

Reto: Contar los pasos de cada algoritmo:

import random

def busqueda_lineal(lista, objetivo):
    """Busqueda lineal"""
    match = False
    pasos = 0

    for elemento in lista:
        pasos += 1
        if elemento == objetivo:
            match = pasos, True
            break
    
    return match


def busqueda_binaria(lista, comienzo, final, objetivo, pasos=0):
    """Busqueda binaria recursiva."""

    pasos += 1
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return pasos, True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, pasos)

    return busqueda_binaria(lista, comienzo, medio - 1, objetivo, pasos)


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, 100) for i in range(tamano_de_lista)]

    # Busqueda lineal
    print("\nBusqueda lineal".upper())
    print(lista)
    pasos, encontrado = busqueda_lineal(lista, objetivo)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista.\n')
    print(f'Hubo {pasos} pasos para la busqueda lineal.\n')

    # Busqueda binaria
    print("\nBusqueda binaria".upper())
    bin_list = sorted(lista)
    print(bin_list)
    pasos_bin, encontrado = busqueda_binaria(bin_list, 0, len(bin_list), objetivo)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista.\n')
    print(f'Hubo {pasos_bin} pasos para la busqueda binaria.')

Output

De que tamaño sera la lista? 100
Que numero quieres encontrar? 80

BUSQUEDA LINEAL
[40, 60, 78, 77, 79, 43, 54, 96, 58, 58, 29, 49, 4, 15, 29, 25, 0, 27, 48, 10, 52, 
26, 29, 37, 47, 42, 71, 36, 40, 76, 77, 48, 30, 50, 1, 41, 81, 46, 49, 22, 0, 29, 3
1, 29, 82, 88, 40, 71, 66, 3, 2, 33, 49, 41, 7, 55, 42, 33, 14, 89, 62, 17, 65, 71,
 6, 57, 99, 32, 58, 51, 37, 78, 49, 87, 6, 98, 83, 67, 66, 75, 45, 80, 42, 68, 100,
 32, 79, 50, 7, 36, 100, 91, 94, 14, 51, 33, 72, 26, 53, 66]
El elemento 80 esta en la lista.

Hubo 82 pasos para la busqueda lineal.

BUSQUEDA BINARIA
[0, 0, 1, 2, 3, 4, 6, 6, 7, 7, 10, 14, 14, 15, 17, 22, 25, 26, 26, 27, 29, 29, 29, 29, 29, 30, 31, 32, 32, 33, 33, 33, 36, 36, 37, 37, 40, 40, 40, 41, 41, 42, 42, 42, 43, 45, 46, 47, 48, 48, 49, 49, 49, 49, 50, 50, 51, 51, 52, 53, 54, 55, 57, 58, 58, 58, 60, 62, 65, 66, 66, 66, 67, 68, 71, 71, 71, 72, 75, 76, 77, 77, 78, 78, 79, 79, 80, 81, 82, 83, 87, 88, 89, 91, 94, 96, 98, 99, 100, 100]
buscando 80 entre 0 y 100
buscando 80 entre 49 y 100
buscando 80 entre 71 y 100
buscando 80 entre 71 y 80
buscando 80 entre 78 y 80
buscando 80 entre 79 y 80
El elemento 80 esta en la lista.

Hubo 6 pasos para la busqueda binaria.

Hola… les comparto mi aporte del código con el conteo de iteraciones:

import random

def busqueda_binaria(lista, comienzo, final, objetivo, count):
  count += 1
  print('iteraciones del algoritmo:', count)
  print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final-1]}')
  if comienzo > final:
    return False
  
  medio = (comienzo + final) // 2

  if lista[medio] == objetivo:
    return True
  
  elif lista[medio] < objetivo:
    return busqueda_binaria(lista, medio+1, final, objetivo, count)
  else:
    return busqueda_binaria(lista, comienzo, medio-1, objetivo, count)


tamaño_de_lista = int(input('De que tamaño es la lista?'))
objetivo = int(input("Que numero desea encontrar?"))



lista = sorted([random.randint(0,100) for i in range (tamaño_de_lista)])

encontrado = busqueda_binaria(lista, 0, len(lista), objetivo,0)

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

Hola a todos!, les comparto mi aporte al reto. Agradezco sus comentarios 😃

import random
from busqueda_binaria import busqueda_binaria
def contadorLineal(lista,objetivo):
    r=0
    for elemento in lista:
        r=r+1
        if elemento==objetivo:
            match=True
            break
        return r
    
def contadorBinario(lista,comienzo,final,objetivo,r=0):
    lista=sorted(lista)
    if comienzo==final and lista[comienzo-1]!=objetivo:
        return r+1
    if comienzo > final:
        return r+1
    medio= (comienzo+final)//2
    if lista[medio]==objetivo:
        r+=1
        return r
    elif lista[medio]< objetivo:
        r+=1
        return contadorBinario(lista,medio+1,final,objetivo,r)
    else:
        r+=1
        return contadorBinario(lista,comienzo,medio-1,objetivo,r)

def diferencia_en_busquedas(nMaxAleatorio,tamano_de_lista,objetivo):
    lista= [random.randint(0,nMaxAleatorio) for i in range(tamano_de_lista)]
    comienzo=0
    final=len(lista)
    nLineal=contadorLineal(lista,objetivo)
    nBinario=contadorBinario(lista,comienzo,final,objetivo)
    encontrado= busqueda_binaria(lista,comienzo,final,objetivo)
    if nLineal > nBinario:
        return f'{"Se encontro" if encontrado else "No se encontro"} en la lista el número {objetivo} y el método de busqueda lineal fue mas eficiente que el binario por {nBinario-nLineal} iteraciones'
    else:
        return f'{"Se encontro" if encontrado else "No se encontro"} en la lista el número  {objetivo} y el método binario fue mas eficiente que el lineal por {nBinario-nLineal} iteraciones'

if __name__ == "__main__":
    tamano_de_lista=int(input('De que tamaño sera la lista? '))
    objetivo=int(input('Que numero quieres encontrar? '))
    nMaxAleatorio=int(input('Número maximo dentro de la lista? '))
    print(diferencia_en_busquedas(nMaxAleatorio,tamano_de_lista,objetivo))

import random


def busqueda_binaria(lista, comienzo, final, objetivo, contador=0):
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    contador += 1

    if comienzo > final:
        print(f'total de pasos {contador} en busqueda binaria')
        return False

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        print(f'total de pasos {contador} en busqueda binaria')
        return True
        

    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, contador)

    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador)


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

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)

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

Pensé que sería mas fácil, pero se logró… cualquier mejora o comentario son bienvenidos!

import random

def busqueda_lineal(lista,objetivo):
    match = False
    contador = 0
    #print(lista)

    for elemento in lista:
        contador += 1
        if elemento == objetivo:
            match = True
            break

    print(f'LINEAL: El valor {objetivo} {"esta" if match else "no esta"} en la lista, se determino en {contador} iteraciones')   
    return contador

def busqueda_binaria(lista, comienzo, final, objetivo, contador):
    match = False
    contador += 1
    if comienzo > final:
        print(f'BINARIO: El valor {objetivo} no esta en la lista, se determino en {contador} pasos')
        return contador
    
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        match = True
        print(f'BINARIO: El valor {objetivo} {"esta" if match else "no esta"} en la lista, se determino en {contador} iteraciones')   
        return contador
    if lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, contador)
    if lista[medio] > objetivo:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))

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

    lineal = busqueda_lineal(lista, objetivo)

    lista = sorted(lista)

    binario = busqueda_binaria(lista, 0, len(lista), objetivo, 0)

    if binario == lineal:
        print(f'Ambos sistemas lograron el resultado en igual cantidad de iteraciones')
    elif binario < lineal:
        print(f'El sistema binario tomo {lineal-binario} pasos menos en resolver la busqueda')
    else:
        print(f'El sistema lineal tomo {binario-lineal} pasos menos en resolver la busqueda')```

Anexo código arreglando el problema de buscar números mayores que la lista generada aleatoreamente

import random

def busqueda_binaria(lista, comienzo, final, objetivo):
    if comienzo > final :
        return False

    print(f'buscando {objetivo} entre Rango:{comienzo} #lista:{lista[comienzo]} y Rango:{final} #lista:{lista[final]}')
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))

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

    encontrado = busqueda_binaria(lista, 0, len(lista)-1, objetivo)

    print(tamano_de_lista)
    print(len(lista)-1)

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

Creo que no se dijo, pero recuerden que la búsqueda binaria es algoritmica porque va dividiendo el conjunto en partes más pequeñas pero constantes: Θ(log(n)). Saludos.

#Busqueda lineal O(n)

import random

def busqueda_lineal(lista,objetivo,contador):
match = False
for elemento in lista: #O(n)
contador += 1
if elemento == objetivo:
match = True
print(f’el numero de iteraciones fue {contador}’)
break

return match

if name == ‘main’:
tamano_de_lista = int(input('De que tamano sera la lista? '))
objetivo = int(input('Que numero quieres encontrar? ‘))
contador = 0
lista = [random.randint(0,100) for i in range(tamano_de_lista)]
encontrado = busqueda_lineal(lista,objetivo,contador)
print(lista)
print(f’El elemento {objetivo}{" esta" if encontrado else " no esta"} en la lista’)

Conforme crece el tamaño de la lista, la diferencia del número de iteraciones necesarias es enorme:

import random
cont_binaria = 0
cont_lineal = 0

def busqueda_binaria(lista, comienzo, final, objetivo):
    global cont_binaria
    cont_binaria += 1

    if comienzo > final:
        return False

    medio = (comienzo + final)//2

    if lista [medio] == objetivo:
        return True
    elif lista [medio] < objetivo:
        return busqueda_binaria (lista, medio + 1, final, objetivo)
    else:
        return busqueda_binaria (lista, comienzo, medio-1, objetivo)

def busqueda_lineal(lista, objetivo):
    global cont_lineal
    match = False

    for elemento in lista:
        if elemento == objetivo:
            cont_lineal += 1
            match = True
            break
        else:
            cont_lineal += 1

    return match


if __name__ == '__main__':
    
    tamano_de_la_lista = int(input('De qué tamaño será la lista? '))
    objetivo = int(input('Qué número quieres encontrar? '))

    lista =  sorted([random.randint(0, 100) for i in range (tamano_de_la_lista)])
    encontrado_bin = busqueda_binaria(lista, 0, len(lista), objetivo)
    encontrado_lin = busqueda_lineal(lista, objetivo)

    print (f'El elemento {objetivo} {"está" if encontrado_bin == True else "no está"} en la lista')
    print (f'Se necesitaron {cont_binaria} iteraciones en búsqueda binaria')
    print (f'Se necesitaron {cont_lineal} iteraciones en búsqueda lineal')

para saber las iteraciones agrege un parametro mas inicializado en 0 que va incrementando cada vez que se vuelve a llamar la funcion

No lo ubiera logrado sin los aportes, Gracias

import random

def busqueda_binaria(lista, comienzo, final, objetivo,contador_binario = 0):
    
    contador_binario += 1
    
    if comienzo > final:
        return False, contador_binario
           
    medio = abs((comienzo + final) // 2)
    
    if lista[medio] == objetivo:
        return True, contador_binario
    
    elif lista[medio] < objetivo:
        
        return busqueda_binaria(lista, medio + 1, final, objetivo, contador_binario = contador_binario)
    
    else:
        
       # print(lista[medio])
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador_binario = contador_binario)
    
def busqueda_lineal(lista, objetivo, contador_lineal = 0):
    match = False
    
    for elemento in lista:
        contador_lineal += 1
        if elemento == objetivo:
            match = True
            break
        
    return match, contador_lineal
    

if __name__ == '__main__':
    
    tamano_de_la_lista = int(input('Ingrese el tamano de la lista => '))
    lista = list(random.randint(0,100) for i in range(tamano_de_la_lista))
    objetivo = int(input('Que numero buscar en la lista => '))
    
    print(lista)
    
    lista_binaria = sorted(lista)
    lista_lineal = lista
    
  
    encontrado_binario = busqueda_binaria(lista_binaria, 0, tamano_de_la_lista, objetivo)
    encontrado_lineal = busqueda_lineal(lista_lineal, objetivo)
    
    encontrado = encontrado_binario and encontrado_lineal
    #print(encontrado)
  
    for i in range(tamano_de_la_lista):
        contador_binario = busqueda_binaria(lista_binaria, 0, tamano_de_la_lista, objetivo)
        contador_lineal = busqueda_lineal(lista_lineal, objetivo)
       
    print(f'El elemento {objetivo} {"fue encontrado" if encontrado else "No se encuentra"} en la lista')
    print(f'El numero de iteraciones de la busqueda binaria fue: {contador_binario}')
    print(f'El numero de iteraciones de la busqueda lineal fue: {contador_lineal}')

para quienes quieran hacer la prueba de tamaño de lista 10 y objetivo 99 y les salga un error aquii esta la solucion y es porque llega un momento a preguntarse si dos numeros on iguales y el error dice que el indice esta fuera de rango…

import random

def busqueda_binaria(lista, comienzo, final, objetivo):
    medio = (comienzo + final)//2
    
    if comienzo > final or medio == final:
        print("comienzo mayor al final")
        return False
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final -1]}')
    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        print("medio < objetivo")
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        print('medio > objetivo')
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)
    

if __name__ == '__main__':
    tamaño_de_lista = int(input("¿De Qué tamaño es la lista? "))
    objetivo = int(input("¿Qué número quieres encontrar? "))
    
    lista = sorted([random.randint(0, 100) for i in range(tamaño_de_lista)])
    
    encontrado =  busqueda_binaria(lista, 0, len(lista), objetivo)
    
    print(lista)
    print(f'el elemento {objetivo} {"esta"  if encontrado else "no esta "} en la lista')

Aquí mis soluciones, simples per hay que poner atención en los detalles, si me tardé en resolverlo porque justamente quería hacer simple la solución
.
Búsqueda lineal

import random

def busqueda_lineal(lista, objetivo, iterador):
    for elemento in lista: #Tenemos un O(n)
        iterador += 1
        if elemento == objetivo:
            return True, iterador
            
    return False, iterador

if __name__ == '__main__':
    tamano_de_lista = int(input('De qué tamaño es la lista? '))
    objetivo = int(input('Qué número quieres encontrar? '))

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

    encontrado, iterador = busqueda_lineal(lista, objetivo, 0)

    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'El número de iteraciones fue de {iterador}')

.
Búsqueda binaria

import random

def busqueda_binaria(lista, comienzo, final, objetivo, iterador):
    iterador += 1
    #print(f'buscando el {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if comienzo > final:
        return False, iterador
    
    medio = (comienzo + final) // 2
    
    if lista[medio] == objetivo:
        return True, iterador
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, iterador)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, iterador)
    
if __name__ == '__main__':
    tamano_de_lista = int(input('De qué tamaño es la lista? '))
    objetivo = int(input('Qué número quieres encontrar? '))

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

    encontrado, iterador = busqueda_binaria(lista, 0, len(lista), objetivo, 0)
        
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'Hubo un total del {iterador} iteraciones')

• Mi aporte:

import random
import time


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

    
    for elemento in lista:
        count_l += 1
        if elemento == objetivo:
            match = True
            break



    return (match, count_l)


def busqueda_binaria(lista, comienzo, final, objetivo, count_b=0):
    count_b += 1
    print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if comienzo >final:
        return (False, count_b)
    
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return (True, count_b)
    elif lista[medio] > objetivo:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, count_b)
    else:
        return busqueda_binaria(lista, medio + 1, final, objetivo, count_b=count_b)




if __name__== '__main__':

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

    lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)])
    print(f'Su lista generada de forma aleatoria es: ',lista)

    #Lineal
    comienzo = time.time()
    (encontrado, count_l) = busqueda_lineal(lista, objetivo)
    final = time.time()
    
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista \n\n')

    tiempo_l = final - comienzo
    print(f"El tiempo de ejecucion de la busqueda lineal es de {tiempo_l} segundos y se iteraron {count_l} veces \n" )


    #Binaria
    comienzo_t = time.time()
    (encontrado, count_b) = busqueda_binaria(lista, 0, len(lista), objetivo)
    final_t = time.time()

    tiempo_b = final_t - comienzo_t
    print(f"El tiempo de ejecucion de la busqueda binaria es de {tiempo_b} segundos y se iteraron {count_b} veces")

uuuuuuf eso de que no existe un buen algoritmo para ordenar suena tanto a calculo y a teoria axiomatica de conjuntos

Revisando el código con chatGPT la complejidad algorítmica es O log(n)

La razón detrás de esta complejidad radica en cómo funciona la búsqueda binaria. En cada paso de la recursión, la búsqueda se reduce a la mitad del espacio de búsqueda restante. Por lo tanto, en cada nivel de recursión, el tamaño del espacio de búsqueda se divide por 2. Esto significa que, en promedio, se necesita la mitad del tiempo para reducir el espacio de búsqueda, lo que resulta en una complejidad logarítmica.

Dado que la búsqueda binaria disminuye el espacio de búsqueda en cada paso y se acerca al objetivo exponencialmente más rápido a medida que aumenta el tamaño de la lista, su complejidad es O(log n), que es mucho más eficiente que la búsqueda lineal (O(n)) en listas no ordenadas.

Por supuesto el Binary Search es mejor, la restricción es que sea ordenada pero es genial este método.

Signature es un término que utiliza el profe en el minuto 5;29 y del cual ChatGPT nos dice:

En programación, la firma (signature en inglés) se refiere a la estructura y características distintivas de una función o método. También se conoce como la declaración de la función. La firma de una función incluye el nombre de la función, los tipos de parámetros que acepta (si los hay) y el tipo de valor de retorno (si corresponde).

import random
n = 0
def busqueda_binaria(lista, comienzo, final, objetivo, iteracion = 0):
    

    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}, Numero de iteraciones: {iteracion }')
    
    #Caso base . No existe el elemento
    if comienzo > final:
        iteracion +=1
        return False, iteracion
        

    medio = (comienzo + final) // 2
    #La mitad es el valor objetivo
    if lista[medio] == objetivo:
        iteracion +=1
        return True, iteracion
    # Realizamos otra bùsqueda binaria para volver a dividir la lista en 2
    elif lista[medio] < objetivo:
        iteracion +=1
        return busqueda_binaria(lista, medio + 1, final, objetivo, iteracion)
    #Nos vamos a la parte de abajo
    else:
        iteracion +=1
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, iteracion)


if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano es la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)

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

Búsqueda Binaria vs Búsqueda Lineal

Peor de los casos en Búsqueda Binaria

Mejor de los casos en Búsqueda Binaria

Paso el codigo que hice, del final de la clase.

import random

def busqueda_binaria(lista, comienzo, final, objetivo, pasos=0):

    print(f'Paso numero {pasos} buscando {objetivo} entre {lista[comienzo]} y {lista[ final - 1  ]}')
    
    if comienzo > final:
        pasos+=1
        return (False, pasos)
    
    medio = (comienzo + final) // 2
    
    if lista[medio] == objetivo:
        pasos+=1
        return (True,pasos)
    
    elif lista[medio] < objetivo:
        pasos+=1
        return busqueda_binaria(lista, medio + 1, final, objetivo, pasos)
    else:
        pasos+=1
        return busqueda_binaria(lista, comienzo, medio-1, objetivo, pasos)

if __name__ == '__main__':
    tamaño_de_la_lista = int(input('De que tamaño es la lista? :'))
    objetivo = int(input('Que numero quieres encontrar? : '))
    
    lista = sorted([random.randint(0,100) for i in range(tamaño_de_la_lista)]) 

    encontrado = busqueda_binaria(lista, 0,len(lista), objetivo) #comienza en 0 y termina en la long de la lista
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    
    

Les comparto mi grafica de tiempos y abajo les agrego la comparación de veces en las que el ciclo se repitió

Linal vs Binario

[399766, 19],
 [56740, 16],
 [36442, 17],
 [138976, 19],
 [184753, 18],
 [387682, 20],
 [309351, 17],
 [140546, 18],
 [123075, 17],
 [204354, 17],
 [119969, 17],

implementación de contador de pasos para la búsqueda binaria

def busqueda_binaria(lista, comienzo, final, objetivo, contador = 0):

#contador de pasos
contador += 1
#print(contador)

print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final-1]}') #porque es por indice el -1

#caso base
if comienzo > final:
    return False

#dividiendo la lista en 2
medio = (comienzo + final)//2 #division de enteros

if lista[medio] == objetivo:
    return contador

elif lista[medio] < objetivo:
     
    return busqueda_binaria(lista, medio + 1 , final, objetivo, contador)

elif lista[medio] > objetivo:
    
    return busqueda_binaria(lista, comienzo , medio - 1, objetivo, contador) 

#si archivo se ejecuta desde la consola se ejecuta main
#sirve para ejecutar un programa de forma directa y que a su vez
#sirva como un modulo para importarlo a otros programas
if name == “main”:
import random
tamaño_de_lista= int(input("de que tamaño será la lista?: "))
objetivo= int(input("que número quieres encontrar: "))

# la busqueda binaria asume que la lista está ordenada 
lista = sorted([random.randint(0,100) for i in range(tamaño_de_lista)])


#debemos usar indices en lugar de hace listas cada vez mas pequeñas
encontrado = (busqueda_binaria(lista, 0, len(lista), objetivo))

print(lista)
print(f'El elemento {objetivo} {"está" if encontrado else "no esta"} en la lista, se realizaron {encontrado} pasos')

Les comparto mi gráfica con los resultados que obtuve utilizando ambos tipos de búsqueda:

import random

def busqueda_binaria(lista, comienzo, final, objetico):
    print(f'busqueda {objetivo} entre {lista[comienzo]} y {lista[final-1]}')
    if comienzo > final:
        return False
    
    medio = (comienzo + final)//2

    if lista[medio]== objetivo:
        return True
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)


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

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

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

import random

def busqueda_binaria(lista, comienzo, final, objetivo, count):
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final -1]}')


    if comienzo > final:
        count+=1
        print(count)
        return False, count
    
    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        count +=1
        print(count)
        return True, count
    elif lista[medio] < objetivo:
        count+=1
        print(count)
        return busqueda_binaria(lista, medio + 1, final, objetivo, count)
    else:
        count+=1
        print(count)
        return busqueda_binaria(lista, comienzo, medio-1, objetivo, count)

    
    

if __name__ == "__main__":
    tamaño_de_lista = int(input('Tamaño de la lista: '))
    objetivo = int(input("Que numero quieres encontrar? "))

    lista = sorted([random.randint(0,100) for i in range(tamaño_de_lista)])
    
    count = 0
    encontrado,count = busqueda_binaria(lista, 0 , len(lista), objetivo,count)
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no está" } en la lista')
    print(f"cantidad de veces {count}")

Hola compañeros…

Hice una prueba yo mismo antes de continuar con la clase, en realidad siento que si es todo un reto hacer esto (ya lo había vito con c )jajaja, comparto mi código y si alguien tiene algún feedback con gusto lo recibiré.

Mi aporte para realizar contador en busqueda binaria

import random
def busqueda_binaria(lista, comienzo, final, objetivo, contador):
    contador += 1
    print(f'buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    if comienzo > final:
        return False,contador

    medio = (comienzo + final) // 2 #division de enteros, sind ecimales
    
    if lista[medio] == objetivo:
        return True,contador
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, contador=contador)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador=contador)
   

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamaño es la lista? '))
    objetivo = int(input('Que numero deseas encontrar? '))
    lista = sorted([random.randint(0,100) for i in range(tamano_de_lista)]) #ordenar list
    encontrado,contador = busqueda_binaria(lista, 0, len(lista), objetivo, contador=0)
    print(lista)
    print(f'El elemento {objetivo} {"esta " if encontrado else "no esta"} en la lista')
    print(f'Iteraciones busqueda binaria => {contador}')

Encontre un bug en el cual si el valor objetivo es mayor al valor más alto que tenga la lista, genera un error ejemplo:

en la lsita [4,14,15,50,81,91] se busca el número 100 genera un error de “index out of range” ya que al dividir y comprobar si es menor le sigue sumando uno antes de calcular medio.

Esto lo solucione añadiendo al primer if una validación más

if comienzo > final or comienzo == len(lista):
	return False

Comparto una solución del reto pero con el programa de Busqueda_lineal

import random

contador = 0

def busqueda_lineal(lista, objetivo):
    match = False

    global contador

    for elemento in lista:
        contador += 1
        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(10, 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')
    print(f"Se hicieron {contador} pasos")

Me costó un poco porque no sabía como hacer un contador en una función recursiva, pero con la ayuda de mis compañeros lo resolví y deje unos apuntes dentro del código

import random

def binary_search(list,start ,end, goal, counter_binary_search=0):

    counter_binary_search +=1
    
    # En este codigo queremos ver la complejidad algoritmica
    # de un codigo de busqueda buranaria

    # Si el comienzo es mayor que final es que quiere decir 
    # que ya nos pasamos y ya no podemos dividir mas la mitad
    # la lista / estructura de datos


    #esto es opcional  
    #print(f'Buscando {goal} entre {list[start]} y {list[end - 1]}')


    if start > end:
        return (False,counter_binary_search)
    
    # La busqueda binaria en pocas palabras es tomar una lista,
    # dividirla por la mitad y ver si nuestro objetivo esta en
    # alguna de las dos mitades, despues se seleciona la mitad
    # que se sabe que esta nuestro objetivo y volvemos a dividirla
    # por la mitad y así sucesivamente

    # Eso nos deja con 3 esenarios posibles:
    # Esta en la primera mitad, Esta en la segunda mitad o 
    # Esta en el medio

    

    middle = (start + end) // 2


    if list[middle] == goal:

        return (True,counter_binary_search)

    elif list[middle] < goal:

        return binary_search(list, middle + 1 , end, goal, counter_binary_search=counter_binary_search)

    else:

        return binary_search(list, start, middle - 1, goal, counter_binary_search=counter_binary_search)


    #nota: // hace divisiones sin decimales



def search_linear(list,goal,counter_search_linear=0):

    # Este codigo es muy simple como hacemos que un ciclo
    # for recorra cada uno de los elementos verificado si
    # es el numero al queremos llegar


    match = False

    for element in list:

        counter_search_linear +=1

        if element == goal:
            match = True
            break

    return (match, counter_search_linear)   

    

if __name__ == '__main__':

    list_size = int(input('De que tamaño será la lista? '))
    goal = int(input('Que numero quieres encontrar? '))

    # Para la busqueda binaria es muy importante que la 
    # list / estrucutara de datos este ordenada 

    list = sorted([random.randint(0,100) for i in range(list_size)])



    (found,counter_binary_search) = binary_search(list,0,len(list),goal)
    (found,counter_search_linear) = search_linear(list,goal)

    #print(list)
    
    print(f'El elemento {goal} {"esta" if found else "no esta"} en la lista')

    # y comparamos cantidad de interaciones

    print(f'La busqueda binaria se tardó {counter_binary_search} iteraciones y')
    print(f'la busqueda lineal se tardó {counter_search_linear} iteraciones')

me parecio facil solo con una variable lobal

import random

contador = 0

def busqueda_binaria(lista, comienzo, final, objetivo):
    
    global contador

    if comienzo > final:
        return False


    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        contador += 1
        return True

    elif lista[medio] < objetivo:
        contador += 1
        return busqueda_binaria(lista, medio + 1, final, objetivo)

    else:
        contador += 1
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo)
         


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

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

    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f' s hicieron {contador} pasos ')

de que tamaño es la lista? 1000
Que numero quieres encontrar? 456
busqueda_binaria 0.0
busqueda_lineal 0.0004093647003173828
El elemento 456 esta en la lista

si bien con la busqueda binaria, pareciera que NO tiene que recorrer toda la lista, si la lista esta desordenada, tiene que aplicar la funcion sorted() que convenientemente la ejecuta fuera de la funcion binaria, digo conveniente porque no nos dice si esta funcion recorre toda la lista para buscarla si eso fuera enrealidad no estas optimizando nada, aun si la funcion sorted() no la recorriera, tendria que tenerla encuenta y no obviar su gasto computacional

Hola quiero aportar algo, como pueden ver en busqueda lineal me dice que el numero 50 NO esta en la lista (linea roja), algo que si es cierto.
Pero en la busqueda binaria (linea amarilla), me dice que el elemento esta en la lista, algo que es falso, ya que a la hora de imprimir la lista aparece los numeros 49, 49, 51, 52, ect. Por lo no tendría que dar ese resultado

Mi teoria es que el codigo del profe esta mal planteado, me explico…
para sacar el medio (linea roja) ocupamos sumar (comienzo + final) // 2
luego… a ese resultado lo comparamos con el objetivo

en ningun momento comparamos los indices de las listas, si no el resultado que nos dio el “medio” algo que nosotros hemos sacado de un calculo y no de comparar los elementos de la lista

Bueno les dejo el codigo por si no es mi teoria y solo escribi algo mal 🙈

import random

def busqueda_lineal(lista, objetivo, cont = 0):
    match = False
    for elemento in lista: # O(n)
        cont += 1
        if elemento == objetivo:
            match = True
            break
    return match, cont

def busqueda_binaria(lista, comienzo, final, objetivo, cont1 = 0):
    if comienzo > final:
        return False, cont1
    
    medio = (comienzo + final) // 2 # // - divicion de enteros
    cont1 += 1

    if lista[medio] == objetivo:
        return True, cont1
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, cont1)
    else: 
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, cont1)

# ------------------------------------------------------------------- #

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tamano sera la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))
    lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)])

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

    
    (encontrado, contador1) = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(contador1)
    print(f'El elemento {objetivo} {"ESTA" if encontrado else "NO esta"} en la lista ')
    #print(lista)

• nota 1: Primero, tiene que ser con un numero de lista pequeño, si ponen que la lista tenga 1’000,000 de elementos van a apareces todos los números y se van a repetir varias veces
• nota 2: se que el medio esta haciendola de indice, solo es una teoria que puede ser refutada facilmente, solo queria su opinión

Si solo se puede buscar en una lista una vez y los elementos de la lista estan desordenados, utilizamos el algoritmo de Busqueda Lineal. Si se puede acudir a la lista varias veces, se puede ordernar y aplicar el algoritmo de Busqueda Binaria.

En general, no existe un buen algoritmo para ordenar. Por tanto si el algoritmo se va a utilizar muchas veces, entonces conviene ordenar la lista y guardarla para luego ejecutar la busqueda las veces que se requieran sobre la lista ya ordenada. De esta manera amortizamos el costo en tiempo que lleva el ordenar la lista cada vez que el algoritmo se ejecute.

Me recuerda al metodo Newton-Raphson para encontrar raices

Yo pondría estos condicionales para evitar algunas iteraciones innecesarias, como ya sabemos cual es el número objetivo, y nuestra lista esta ordenada de menor a mayor, sería algo como esto:

if inicio > final or lista[inicio] == lista[final - 1] or objetivo < lista[inicio] or objetivo > lista[final - 1]:
        return False

if lista[inicio] == objetivo or lista[final - 1] == objetivo:
        return True

En algunas ocasiones el número a buscar puede ser menor o mayor a los números de la lista, entonces si cumple esto, evidentemente no estará ya que sabemos el número inicial y el número final de nuestra lista porque esta ordenada.

En otras ocasiones el número puede estar al comienzo o al final y el algoritmo al calcular la media no se dará cuenta hasta una siguiente iteración. con eso se puede ahorrar una iteración más

hola gente, pequeño aporte ya que el programa me lanzaba error a veces, en el primer IF modifque lo siguiente:

agregue como condiciones:

“OR lista[comienzo] == objetivo OR lista[final-1] == objetivo”

De esta forma cuando encuenta el numero tanto en el medio como el comienzo o final retorna True

• Este Proyectito busca comparar la eficiencia que hay entre la busqueda lineal y la busqueda binaria. en 100 busquedas cada uno
  
  como podemos ver la diferencia es aproximadamente 5 veces mas lenta en la lineal.

#-------------Busqueda Lineal-------------
import random

def busquedalineal(lista,objetive):
    match = False
    cuentapasos = 0
    for element in lista:
        cuentapasos+=1
        if element == objetive:
            break

    return cuentapasos

if __name__ == '__main__':
    contador = 0    
    contadorfinal= []
    while contador!=100:
        
        
        objetive = random.randint(1,51) # el objetivo a buscar debe ser aleatorio para una evaluacion mas objetiva de la eficiencia de este tipo de busqueda
        lista = [i for i in range(51)] # la lista es siempre la misma del 1 al 50
        encontrado = busquedalineal(lista, objetive) 
        contadorfinal.append(encontrado)
        
        print(f"se encontro el ojetivo en {encontrado}")
        contador += 1
    print(f"en un proceso de 100 iteraciones de busqueda LINEAL se encontraron \n los objetivos en un total de {sum(contadorfinal)} pasos")
     

#------------------------Busqueda Binaria-------------------

def binarySearch(n):
    lista = [i for i in range(51)]
    start = 0
    cuentapasos = 0
    final = len(lista) - 1 
    while start<=final:
        cuentapasos+=1
        pointer = (start+final)//2
        if n == lista[pointer]:
            break
        elif n > lista[pointer]:
            start = pointer + 1
        else:
            final = pointer - 1
    return cuentapasos
             
if __name__=="__main__":
    contador_de_vueltas = 0    
    contadorfinal= []
    while contador_de_vueltas!=100:    
        num =  random.randint(1,51)
        encontrado =  binarySearch(num)
        contadorfinal.append(encontrado)
        print(f"se encontro el ojetivo en {encontrado}")
        contador_de_vueltas += 1
    print(f"en un proceso de 100 iteraciones de busqueda BINARIA se encontraron \n los objetivos en un total de {sum(contadorfinal)} pasos")
    

• En la implementación realizada por el docente encontré una falla cuando el objetivo es mayor al último elemento de la lista.

objetivo  = 5
lista = [0, 1, 2, 3]

• Mi implementación sin recursividad:

import random


def busqueda_binaria(lista: list, objetivo: int):
    """Lista: La lista tiene que estar ordenada"""
    iteraciones = 0
    encontrado = False
    bajo = 0
    alto = len(lista) - 1
    while bajo <= alto:
        iteraciones += 1
        index_mitad = (alto + bajo) // 2  # division de entero
        print(f'bajo={bajo}, alto={alto},index_mitad={index_mitad}')
        valor = lista[index_mitad]
        print(f'valor={valor}')
        if valor == objetivo:
            encontrado = True
            break
        elif objetivo > valor:
            bajo = index_mitad + 1
        else:
            alto = index_mitad - 1
    return encontrado, iteraciones


if __name__ == '__main__':
    tamano_lista = int(input('Ingrese el tamaño de la lista: '))
    objetivo = int(input('Ingrese el número a buscar: '))

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

    print(lista)

    encontrado, iteraciones = busqueda_binaria(lista, objetivo)
    print(
        f'Objetivo: {objetivo} '
        f'{"está en la lista" if encontrado else "no encontrado"}\n'
        f'Iteraciones: {iteraciones}'
    )

Ejercicio del Reto con algunos ajustes, cualquier sugerencia o corrección es siempre bienvenida!

from random import randint


def busqueda_lineal(lista, objetivo):

    contador = 0
    match = False                   

    for elemento in lista:

        contador += 1
        
        if elemento == objetivo:
            match = True
            break

    return match, contador


def busqueda_binaria(lista, comienzo, final, objetivo, contador):

    contador += 1
    if comienzo > final:
        return False, contador

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True, contador
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, contador)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador)


def run():
    
    tamano_de_lista = int(input('De que tamano sera la lista? '))
    objetivo = int(input('Que numeros quieres encontrar? '))

    lista = [randint(0,100) for i in range(tamano_de_lista)]
    (encontrado, contador) = busqueda_lineal(lista, objetivo)
    print('\n*** Busqueda Lineal ***\n')
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista, \n y se realizaron {contador} iteraciones')

    lista = sorted(lista)
    (encontrado, contador) = busqueda_binaria(lista, 0, len(lista), objetivo, 0)
    print('\n*** Busqueda Binaria ***\n')
    print(lista)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista, \n y se realizaron {contador} iteraciones')


if __name__ == '__main__':
    run() 

Va mi aporte, tiene una pequeña corrección para que acepte la búsqueda de números fuera de rango de 0 a 100.

<code> 

import random


def busqueda_lineal(lista, objetivo):

    global contador
    match = False

    for element in lista:
        contador += 1
        if element == objetivo:
            match = True
            break
    return match


def busqueda_binaria(lista, init, end, objetivo):

    #print(f'buscando {objetivo} desde {init} a {end}')    
    global contador
    contador +=1

    if init == end:
        return False
    
    midle = (init + end) // 2

    if lista[midle] == objetivo:
        return True
    elif lista[midle] < objetivo:
        return busqueda_binaria(lista, midle + 1, end, objetivo)
    else:
        return busqueda_binaria(lista, init, midle, objetivo)


if __name__=="__main__":
    tamano_lista = int(input('tamaño de la lista: '))
    objetivo = int(input('Qué número quieres encontrar: '))

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

    print('busqueda binaria')
    contador = 0
    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(f'''Ciclos de busqueda {contador}, 
    {"encontrado" if encontrado else "no encontrado"}''')

    print('busqueda lineal')
    contador = 0
    encontrado = busqueda_lineal(lista, objetivo)
    print(f'''Ciclos de busqueda {contador}, 
    {"encontrado" if encontrado else "no encontrado"}''')

import random

def busqueda_binaria(lista, comienzo, final, objetivo):
print(f’buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}’)
if comienzo > final:
return False
global contador

medio = (comienzo + final) // 2

if lista[medio] == objetivo:
    contador += 1
    return True
elif lista[medio] < objetivo:
    contador += 1
    return busqueda_binaria(lista, medio + 1, final, objetivo)
else:
    contador += 1
    return busqueda_binaria(lista, comienzo, medio - 1, objetivo)

if name == ‘main’:
tamano_de_lista = int(input('De que tamano es la lista? '))
objetivo = int(input('Que numero quieres encontrar? '))
contador = 0
lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista)])

encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)

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

Implementación del algorimo sin recursividad:

def binary_search(lista, objetivo):
	comienzo = 0
	final = len(lista) - 1

	while comienzo <= final:
		medio = (comienzo + final) // 2

		if lista[medio] == objetivo:
			return True

		if lista[medio] < objetivo:
			comienzo = medio + 1
		else:
			final = medio - 1

	return False

Mi aporte de clase. Modifique el código utilizando clases y herencias.

El resultado final muestra si el objetivo fue encontrado y la cantidad de iteraciones

from random import randint

class Busqueda:
    lista = list
    objetivo = int
    
    def __init__(self, lista, objetivo):
        self.lista = lista
        self.objetivo = objetivo
    
    def imprimir_lista(self):
        print(self.lista)
        
    def imprimir_resultado(self, response):
        print(f'El elemento {self.objetivo}', end = ' ')
        print(f'{"esta" if response["is_success"] else "no esta"} en la lista', end = ' ')
        print(f'y tomo {response["iterations"]} iteraciones')


class Lineal(Busqueda):
    
    def __init__(self, lista, objetivo):
        super().__init__(lista, objetivo)
    
    def buscar_objetivo(self):
        is_suscess = False
        iterations = 0
        
        for elemento in self.lista:
            iterations += 1
            if elemento == self.objetivo:
                is_suscess = True
                break
            
        response = {
            'is_success': is_suscess,
            'iterations': iterations
        }
        
        self.imprimir_resultado(response)
    
    
class Binaria(Busqueda):
    
    def __init__(self, lista, objetivo):
        lista_ordenada = sorted(lista)
        super().__init__(lista_ordenada, objetivo)


    def buscar_objetivo(self):
        comienzo, final = [0, len(self.lista)-1]
        is_suscess, iterations = [False, 0]
        
        is_suscess, iterations = self.__buscar_objetivo_r(comienzo, final, iterations)

        response = {
            'is_success': is_suscess,
            'iterations': iterations
        }

        self.imprimir_resultado(response)    
        

    def __buscar_objetivo_r(self, comienzo, final, iterations):
        is_suscess = False
        iterations += 1

        if comienzo > final:
            is_suscess =  False
        else:
            medio = (comienzo + final) // 2
            
            if self.lista[medio] ==  self.objetivo:
                is_suscess = True
            elif self.lista[medio] < self.objetivo:
                is_suscess, iterations = self.__buscar_objetivo_r(medio + 1, final, iterations)
            else:
                is_suscess, iterations = self.__buscar_objetivo_r(comienzo, medio - 1, iterations)
                
        return is_suscess, iterations

    
def main():
    tamano_de_lista = int(input('Ingrese el tamano de la listar: '))
    objetivo = int(input('Que numero quieres encontrar?: '))
    
    lista = [randint(0, 100) for i in range(tamano_de_lista)]
    
    metodo_lineal   = Lineal(lista, objetivo)
    metodo_lineal.buscar_objetivo()
   
    metodo_binario = Binaria(lista, objetivo)
    metodo_binario.buscar_objetivo()
    


if __name__ == '__main__':
    main()

Este es mi modificación del código con los contadores para ver el número de iteraciones en cada algoritmo

import random


def busqueda_lineal(lista, objetivo):
    match = False
    i = 0
    for elemento in lista:  # O(n)
        i += 1
        if elemento == objetivo:
            match = True
            break

    return match, i


def busqueda_binaria(lista, comienzo, final, objetivo, i = 1):
    if comienzo > final:
        return False

    medio = (comienzo + final) // 2

    if lista[medio] == objetivo:
        return True, i
    elif lista[medio] < objetivo:
        return busqueda_binaria(lista, medio + 1, final, objetivo, i + 1)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, i + 1)


if __name__ == '__main__':

    # Para búsqueda lineal
    tamano_de_lista = int(input('De que tamano sera la lista? '))
    objetivo = int(input('Que numero quieres encontrar? '))

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

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

    encontrado, i = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    print(f'Se usaron {i} iteraciones')

Mi código final de esta clase:

# BUSQUEDA BINARIA
# DIVIDE Y CONQUISTA
# SE DIVIDE EN DOS EN CADA ITERACION
# ASUME QUE ESTÁ ORDENADA LA LISTA

# cada uno de los elementos de manera secuancial
import random

def busq_bin(lista, comienzo, final, objetivo, i=0):
    print(f"Iteración numero: {i+1}")
    print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final]}')
    if comienzo > final:
        return False
    medio = (comienzo + final) // 2
    if lista[medio] == objetivo:
        return True
    elif lista[medio] < objetivo:
        i += 1
        return busq_bin(lista, medio + 1, final, objetivo, i)
    else:
        i += 1
        return busq_bin(lista, comienzo, medio-1, objetivo, i)      

if __name__ == '__main__':
    tamano_de_lista = int(input('Ingrese el tamaño de la lista: '))
    objetivo = int(input('Ingresa el numero a buscar: '))
lista = sorted([random.randint(0, 100) for i in range(tamano_de_lista) ])
encontrado = busq_bin(lista, 0, len(lista)-1, objetivo)
print(lista)
print(f'El elemento {objetivo} {"está" if encontrado else "no está"} en la lista.')