Aún no tienes acceso a esta clase

Crea una cuenta y continúa viendo este curso

Búsqueda binaria

16/25
Recursos

Aportes 342

Preguntas 63

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesión.

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

Aquí el gif de animación de la comparación de la búsqueda lineal Vs Binaria

https://miro.medium.com/max/1200/1*4poxx4vMDQfGEq3HeswJoA.gif

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

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

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.

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.

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.

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

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

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:

[email protected] 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')

Las pastillas de matrix de Morfeo
Tiempo vs Memoria

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

Que tal compañeros, de esta manera pueden generar una lista sin elementos repetidos:
![](

Me parecio interesante desarrollar la búsqueda binaria dentro de un bucle while. Imprime la cantidad de pasos y los valores de referencia en cada uno.

def busqueda_binaria(lista_ordenada,valor):

    position = -1

    inicio = 0
    fin = len(lista_ordenada)-1
    medio = (inicio + fin) // 2
    num_paso = 0
    
    while inicio <= fin and position == -1:

        num_paso+=1
        print(f'Paso numero: {num_paso}')
        print(f'Se busca entre pos.inicio {inicio} y pos.fin {fin}')
        print(f'Posicion medio: {medio}, Valor[medio] = {lista_ordenada[medio]}\n')
        if lista_ordenada[medio] == valor:
            position = medio
            
        elif lista_ordenada[medio] < valor:
            inicio = medio+1
            medio = (inicio + fin)//2

        elif lista_ordenada[medio] > valor:
            fin = medio-1
            medio = (inicio + fin)//2        
    
    return position
import random




def binary_search(lists, first_index, last_index, objective, inter = 0):
    print(f'Searching {objective}  into {lists[first_index]} and {lists[last_index - 1]}')
    if first_index > last_index:
        return False

    middle = (first_index + last_index) // 2

    if lists[middle] == objective:
        return True, inter + 1
    elif lists[middle] < objective:
        return binary_search(lists, middle + 1, last_index,  objective, inter + 1)
    else:
        return binary_search(lists, first_index, middle - 1, objective, inter + 1)




if __name__ == '__main__':

    size_list = int(input('How large is the list > '))
    objective = int(input('What number are you looking for > '))

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

    found, inter = binary_search(lists, 0, len(lists), objective)


    print(lists)
    print(f'The element {objective} {"is" if found else "not found"} in the list')
    print(inter)
import random


def  lineal_search(list, objective):
    match = False
    count = 0
    for element in list:
        if element is objective:
            match = True
            break
        count += 1
    return match, count


if __name__ == '__main__':

    size_list = int(input('How large is the list > '))
    objective = int(input('What number are you looking for > '))

    lists = [random.randint(0, 100) for i in range(size_list)]
    
    found, count = lineal_search(lists, objective)


    print(f'The element {objective} {"is" if found else "not found"} in the list')
    print(count)

El algoritmo de búsqueda binaria siempre comprueba el elemento medio de la matriz. Este algoritmo busca el elemento en un matriz ordenada.

El algoritmo de búsqueda binaria itera sobre la matriz y verifica el elemento del medio, si lo encuentra, luego detiene el programa. De lo contrario, si el elemento intermedio es menor que el elemento requerido, omite la parte izquierda de la matriz del elemento intermedio de la búsqueda. De lo contrario, si el elemento intermedio es mayor que el elemento requerido, omite la parte derecha de la matriz del elemento intermedio de la búsqueda.

En cada iteración, el algoritmo de búsqueda binaria reduce el área para buscar el elemento. Por tanto, el número de comprobaciones es menor que el número de comprobaciones realizadas en el algoritmo de búsqueda lineal.

La complejidad temporal del algoritmo de búsqueda binaria es O (log n). En cada iteración, la longitud del área de búsqueda se reduce a la mitad. Se está reduciendo exponencialmente.

Mi aporte: Se nota considerablemente que la búsqueda binaria es por mucho más optima

import random

count = 0

def busqueda_lineal(lista_l, objetivo, count=0):
    match = False

    for elemento in lista_l: # O(n)
        count += 1
        if elemento == objetivo:
            match = True
            break
    return (match, count)

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

    medio = (comienzo + final) // 2

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

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

    lista_l = [random.randint(0, 10000) for i in range(tamano_de_lista)]
    lista_b = sorted(lista_l)

    (encontrado_l, count) = busqueda_lineal(lista_l, objetivo)
    print(f'Iteraciones con búsqueda lineal: {count}')

    (encontrado_b, countb) = busqueda_binaria(lista_b, 0, len(lista_b), objetivo)
    print(f'Iteraciones con búsqueda binaria: {countb}')
    
    print(f'El elemento {objetivo} {"esta" if encontrado_b else "no esta"} en la lista')

De que tamano es la lista?: 1000000
Que numero quieres encontrar?: 2456
Iteraciones con búsqueda lineal: 15813
Iteraciones con búsqueda binaria: 12
El elemento 2456 esta en la lista

[](

Se nota mucho la diferencia:

import random

def busqueda_lineal(lista, objetivo,contador2=0):
    match= False
    #Buscar algún match
    for elemento in lista:
        contador2 +=1
        if elemento==objetivo:
            match=True
            break
    
    return (match,contador2)


def busqueda_binaria(lista, comienzo, final, objetivo,contador=0):
    contador+=1
    #Si comienzo es mayor a final significa que no recorrio toda la lista y no se encontró el valor
    #Si no entra es porque aún podemos continuar
    if comienzo>final:
        return (False,contador)
    #Se define el medio de la lista. El // dice que solo nos importa la parte entera
    medio=(comienzo+final)//2
    #Si se encontró el valor, entonces salir con true
    #Si el medio es menor que el objetivo, el nuevo comiezo es el medio+1 para acortar la lista
    #Si el medio es mayor al objetivo, el nuevo final es medio-1 para acortar la lista
    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)
    #Se hace el número de veces que sea necesario para retornar un valor True o False.

if __name__=="__main__":
    #Pedir info al usuario
    tamano_De_lista=int(input("De que tamaño será la lista? "))
    objetivo=int(input("Que numero quieres encontrar? "))

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

    (encontrado,contador2)=busqueda_lineal(lista,objetivo)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    
    (encontrado,contador)=busqueda_binaria(lista2, 0, len(lista2), objetivo)
    print(f'El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')
    
    print(f"El número de iteraciones con el metodo binario fue {contador}")
    print(f"El número de iteraciones con el metodo lineal fue {contador2}")

Para hacer una prueba mas acida, hice que ambas busquedas usaran la misma lista, solo que la de la binaria esta organizada y la de la lineal esta desorganizada.

Adjunto mi código
import random
from re import match
from typing import Match

class Searcher:

def __init__(self):
    self._counter = 0

@property
def Counter(self):
    return self._counter

def lineal_search(self,list, target):
    match = False
    for element in list:
        match = element == target
        self._counter += 1
        if match:
            break

    return match

def binary_search(self,list,lowerIndex,higherIndex,target):
    if lowerIndex > higherIndex:
        return False

    middle = (lowerIndex + higherIndex) // 2
    self._counter += 1
    print(f'Intento #{self._counter}. Buscando {target} entre {list[lowerIndex]} y {list[higherIndex - 1]}')

    if list[middle]==target:
        return True
    elif list[middle]<target:
        return self.binary_search(list,middle+1,higherIndex,target)
    else:
        return self.binary_search(list,lowerIndex,middle-1,target)

if name==‘main’:
size_list = int(input(“What is the size of list?”))
target = int(input(“What number do you find?”))

searcher = Searcher()

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

#match = searcher.lineal_search(list,target)
match = searcher.binary_search(list,0,len(list),target)

print(list)
print(f'El elemento {target} {"está" if match else "no está"} en la lista. Número de intentos: {searcher.Counter}')

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.

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.

lineal

binario

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

    lista = [random.randint(0, 99999999999) for i in range(tamano_lista)]
    print("Inicio de busqueda Lineal")
    inicio = time.time()
    encontrado_lineal = busqueda_lineal(lista, objetivo)
    final = time.time()
    print(f'El elemento en busqueda lineal {objetivo} {"esta" if encontrado_lineal else "No esta"} en la lista')
    print(f"Fin de busqueda lineal, el computo tardo {final - inicio}")
    print("Inicio de busqueda binaria")
    inicio = time.time()
    encontrado_binaria = busqueda_binaria(lista, 0, len(lista), objetivo)
    final = time.time()
    print(f'El elemento en busqueda binaria {objetivo} {"esta" if encontrado_binaria else "No esta"} en la lista')
    print(f"Fin de busqueda binaria, el computo tardo {final - inicio}")

Busqueda binaria:

import random


def busqueda_binaria(lista, comienzo, final, objetivo, contador=0):
    contador_inter = contador
    contador_inter += 1
    print(f'Buscando {objetivo} entre {lista[comienzo]} y {lista[final - 1]}')
    print(f'Paso {contador_inter}')
    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, contador_inter)
    else:
        return busqueda_binaria(lista, comienzo, medio - 1, objetivo, contador_inter)


if __name__ == "__main__":    
        
    tamano_de_la_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_la_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')

Busqueda lineal:

import random

def busqueda_lineal(lista, objetivo):
    match = False

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

    print(f'Pasos: {contador}')
    return match


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

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

import random

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

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

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

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

    return match, cont_bl


if __name__ == '__main__':
    tamano_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_lista)])
    # print(lista)
    
    encontrado, cont_bb = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(f'BB: El elemento {objetivo} {"esta" if encontrado else "no esta"} en la lista')

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

    print(f'Iteraciones con Busqueda Binaria: {cont_bb}')
    print(f'Iteraciones con Busqueda Lineal: {cont_bl}')

Buenas os adjunto mi código, en este realizo la búsqueda binaria y devuelvo el índice del elemento, en caso de no encontrarlo devuelve -1:

from random import randint

def binary_search(numbers, low, high, target):
    if low > high:
        return -1
    
    mid = (low + high)//2
    if numbers[mid] == target:
        return mid
    elif numbers[mid] > target:
        return binary_search(numbers, low, mid - 1, target)
    else:
        return binary_search(numbers, mid + 1, high, target)


def run():
    size = int(input('Insert list size: '))
    target = int(input('Which number do you want to find?: '))
    random_list = sorted([randint(1, size) for i in range(1, size)])
    index = binary_search(random_list, 0, size, target)
    print(f'The list number is: {random_list}')
    print(f'The number {target} was {"not found" if index == -1 else f"found in the position {index}"}')


if __name__ == "__main__":
    run()
  

Es buena práctica siempre usar un solo return los linters los recomiendan

# Búsquedad binaria, la lista debe estar ordenada
def binary_search(list, init, final, target):
    match = False
    if init < final:
        medium = (init + final) // 2 # '//' significa división de enteros

        if list[medium] == target:
            match = True
        elif list[medium] < target:
            match = binary_search(list, medium + 1, final, target)
        else: # list[medium] > target
            match = binary_search(list, 0, medium - 1, target)

    return match

Si quieren aprender más sobre cómo analizar la compejidad, encontré hace unos momentos este canal en Youtube y explica (a mi parecer bien)
https://www.youtube.com/watch?v=HU4wJzqjCw0&list=PLdohUdAA5bQCKOb0GakTeCaWbcTx90FZt&index=1

Busqueda binaria pero función recursiva, mmmm, jajaja es broma.

Al ejecutar el algoritmo con la condiciones que están en la función busqueda_binaria( ) , nunca se va a ejecutar la condición:

if comienzo > final:
        return False

Porque estamos haciendo comparación de estás variables y la variable comienzo que le pasamos siempre va a ser menor que la variable final y al algoritmo va a seguir iterando así la lista en el indice comienzo sea mayor a la lista en indice final.

Debemos programar la variable comienzo y final como indices de la lista

if lista[comienzo] > lista[final-1]:
        return False

Dejando de iterar cuando el número de la lista en el indice comienzo sea mayor al número de la lista en el indice final.

Viendo lo aprendido hasta ahora de una mejor medición de los recursos que tomaría el algoritmo resolviendo este problema.

Podríamos utilizar el manejo de errores para aquellas ocasiones en las que el usuario ingrese un objetivo mayor a los elementos en la lista (en este caso, 100). La función quedaría algo así.

def busqueda_binaria(list_, start, finish, objective):
    try:
        
        if start > finish:
            return False
        
        middle = (start + finish) // 2
        
        if list_[middle] == objective:
            return True
        elif list_[middle] > objective:
            return busqueda_binaria(list_, start, middle - 1, objective)
        else:
            return busqueda_binaria(list_, middle + 1, finish, objective)
    except IndexError:
        return False
def busqueda_lineal(lista, objetivo):
	match = False
	count = 0

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

	print('Se hacern estos movimientos', count)
	return match
  • Divide y conquista.
  • El problema se divide en 2 en cada iteración.
  • ¿Cuál es el peor caso?
  • Este algoritmo asume que la lista está ordenada, la verdad no existe un buen algoritmo para ordenar,
  • Si se va a utilizar muchas veces el algoritmo quizás si valga la pena ordenarlo y guardarlo y ejecutar la búsqueda. Significa que estamos “amortizando” el costo que se tarda en ordenar una lista.

En resumen:

x = tamaño_lista
big O =>  Log(x)  

son los pasos necesarios para solucionarlo en el peor de los casos.

El peor caso es cuando se ejecuta todo el algotirmo:

   2 > x·(1/2)^n >= 1

siendo x el tamaño de la lista, la n seria el número máximo de pasos, solo hay que despejar la n y más o menos da la solución mala.

la solución seria algo parecido ah.

n = (log(x) / log(2)) + constante ~ log(x)

o viendo con BIG O, O(log(x))

Espero que este bien, aun no vi la clase XD
si me equivoque porngo un comentario.

+2

Cuando pensamos de manera iterativa, hablamos de los stack frames, esos frames se refieren a cada marco o cada llamada que se hace. Entender qué pasa cada vez, hace la diferencia.

off by one, o creo que fail by one, es fallar por uno.

Dentro de la búsqueda binaria recursiva, tenemos que cuando llamamos de nuevo la función, esta en los parámetros, no contiene los ya dados, sino que cambiamos mitad, por el comienzo o la mitad por el final. Esto en diferentes casos.

Es una forma de escribir código, escribir primero el signature, pensando en los parámetros que le damos. Para luego proceder a realizarla.

La búsqueda binaria, se toma rápidamente el mínimo, la mitad y luego el máximo, partiendo hasta encontrar el valor.

Dentro de nuestro trabajo, se encuentra el pensar en qué aspectos priorizamos: Tiempo o Espacio? Si la respuesta es tiempo, vamos a necesitar más espacio en memoria. Si la respuesta es Espacio, vamos a tomarnos más tiempo. Así que hay que entender esto, para tomar bien las desiciones sobre nuestras soluciones.

Cuando nosotros hablamos de utilidad, hablamos de lo práctico que se vuelve, el tomar algunas desiciones. Como en la que ordenamos primero, en caso de usar mucho, un algoritmo de búsqueda y en los que hacemos una sola pasada y no es necesario hacer nada.

El algoritmo de búsqueda binaria, asume que la lista está ordenada.

La búsqueda binaria, está basada en el concepto de divide and conquer, osea divide y vencerás, en las que hacemos el problema tan chico que es lógica cada una de sus soluciones.

Esta implementación funciona de manera estable con listas pequeñas y objetivos en el borde

import random

def busqueda_binaria(lista, objetivo):
    inicio = 0
    mitad = int()
    final = len(lista)
    encontrado = False
    
    while (mitad != final):
        mitad = (inicio + final) // 2
        if objetivo == lista[mitad]:
            encontrado = True
            break
        elif objetivo < lista[mitad]:
            final = mitad - 1
        else:
            inicio = mitad + 1
    return encontrado

tamanio_lista = 20
objetivo = 13
lista = sorted([random.randint(0, 20) for i in range(tamanio_lista)])
#lista.sort() #sin sorted(...) y esta linea también funciona
print('Lista:', lista)
encontrado = busqueda_binaria(lista, objetivo)
print(f'El objetivo: {objetivo}, {"SI" if encontrado else "NO"} se encuentra en la lista')

La implementación del algoritmo presenta problemas, no funciona si el tamaño de la lista es pequeño y el valor objetivo está cerca a los bordes ésta.

Qué barbaridad lo poco que se demora la búsqueda binaria, su única desventaja es la obligación de que el algoritmo esté ordenado.

Esta es mi solución al reto final, lo que hice fue agregar contador como argumento de la función con un valor por defecto igual a 1 y aumentar su valor en cada if donde el valor del medio no era igual al objetivo:

import random

def busqueda_binaria (list, start, end, target, contador=1):
    print(f'Buscando el {target} entre {list[start]} y {list[end-1]}. iteración: {contador}')
    if start > end:
        return False
    mid= (start + end) // 2
    if list[mid] == target:
        return True
    elif list[mid] < target:
        contador+=1
        return busqueda_binaria(list, mid+1, end, target, contador)
    elif list[mid] > target:
        contador+=1
        return busqueda_binaria(list, start, mid-1, target, contador)


if __name__== '__main__':
    size_list = int(input('Indica el tamaño de la lista:\n'))
    objetivo = int(input('Por favor indica el número que quieres encontrar:\n'))
    lista= sorted([random.randint(0,100) for i in range (size_list)])
    encontrado = busqueda_binaria(lista, 0, len(lista), objetivo)
    print(lista)
    print(f'El elemento {objetivo} {"está" if encontrado else "no está"} En la lista')

Les comparto un vídeo donde se explica el algoritmo de búsqueda lineal es muy gráfico y fácil de entender una vez has visto la teoría y requieres de un ejemplo que te afiance el concepto. AlgoRythmics- Bynary search
Aparte de eso explican en su canal otros algoritmos usando el mismo estilo.

Sistema de pasos en busqueda lineal:

def linear_search(list_p, target, steps = 0):
  match = {'found': False, 'steps': steps}

  for element in list_p: # O(n)
    steps += 1
    if element == target:
      match = {'found': True, 'steps': steps}
      break
  
  return match


#Resultados
What size will be the list? 200
What number are u looking for? 48
Looking for 48 between 1 and 99
Looking for 48 between 1 and 49
Looking for 48 between 21 and 49
Looking for 48 between 35 and 49
Looking for 48 between 40 and 49
Looking for 48 between 44 and 49
Looking for 48 between 47 and 49
[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 20, 20, 20, 21, 21, 22, 23, 23, 24, 24, 26, 26, 26, 28, 28, 28, 30, 30, 30, 30, 31, 31, 33, 33, 34, 34, 34, 35, 35, 35, 35, 36, 36, 36, 36, 37, 37, 37, 38, 38, 38, 40, 40, 40, 40, 41, 41, 44, 44, 44, 47, 48, 49, 50, 50, 51, 51, 52, 54, 56, 57, 57, 59, 59, 60, 60, 61, 61, 61, 61, 64, 64, 65, 65, 65, 65, 66, 66, 66, 66, 68, 69, 69, 69, 70, 70, 70, 71, 71, 71, 72, 72, 73, 74, 74, 74, 75, 75, 76, 76, 76, 77, 78, 78, 78, 78, 79, 79, 80, 80, 80, 81, 82, 82, 83, 84, 84, 86, 86, 87, 87, 88, 89, 89, 89, 89, 89, 89, 90, 90, 91, 91, 91, 91, 92, 93, 94, 96, 96, 96, 96, 97, 97, 97, 97, 97, 98, 98, 98, 98, 99, 99, 99, 99]
{'found': True, 'steps': 7}

.
Sistema de pasos en busqueda binaria:

def binary_search(list_p, start, end, target, steps = 0):
  print(f'Looking for {target} between {list_p[start]} and {list_p[end]}')

  if start > end:
    return {'found': False, 'steps': steps}
  
  medio = (start + end) // 2

  if list_p[medio] == target:
    steps += 1
    return {'found': True, 'steps': steps}
  elif list_p[medio] < target:
    steps += 1
    return binary_search(list_p, medio + 1, end, target, steps)
  else:
    steps += 1
    return binary_search(list_p, start, medio - 1, target, steps)



# Resultados
What size will be the list? 200
What number are u looking for? 48
[65, 15, 91, 1, 49, 55, 90, 66, 56, 76, 54, 51, 69, 43, 90, 95, 74, 11, 76, 65, 49, 89, 76, 15, 34, 54, 19, 82, 6, 20, 67, 76, 7, 97, 26, 36, 97, 54, 23, 16, 25, 58, 83, 70, 45, 92, 56, 99, 12, 25, 55, 72, 41, 43, 11, 71, 3, 91, 15, 16, 44, 45, 94, 57, 51, 19, 60, 35, 12, 37, 46, 14, 50, 70, 67, 48, 33, 82, 80, 7, 82, 45, 91, 72, 33, 60, 99, 75, 19, 45, 44, 89, 59, 72, 59, 53, 51, 60, 3, 94, 72, 46, 5, 44, 58, 26, 55, 8, 91, 25, 30, 50, 6, 91, 100, 67, 89, 55, 69, 7, 98, 10, 81, 50, 65, 28, 11, 38, 53, 85, 95, 42, 25, 22, 33, 23, 38, 76, 6, 59, 19, 5, 97, 10, 80, 47, 89, 31, 81, 76, 42, 23, 14, 97, 70, 19, 94, 42, 83, 29, 42, 56, 44, 18, 97, 23, 51, 92, 24, 33, 83, 72, 40, 14, 49, 89, 36, 69, 41, 56, 78, 6, 55, 35, 19, 71, 92, 18, 32, 93, 55, 29, 35, 8, 47, 28, 64, 22, 4, 16]
{'found': True, 'steps': 76}