Búsqueda Binaria en Python: Implementación Recursiva y Iterativa

Clase 31 de 49 • Curso Práctico de Python: Creación de un CRUD

Resumen

¿Cómo implementar una búsqueda binaria en Python?

La implementación de algoritmos en Python, como la búsqueda binaria, no solo optimiza procesos, sino que también desafía tus habilidades de programación. Aquí te guiaré a través de la implementación de la búsqueda binaria desde cero, utilizando Python y técnicas sofisticadas como la recursión. Prepárate para expandir tu arsenal de técnicas algorítmicas.

¿Cómo configurar el entorno inicial?

Para comenzar, crea un archivo nuevo en Python para tu algoritmo de búsqueda. La estructura de tu programa empieza con un punto de entrada, definido por el bloque if __name__ == "__main__":. A continuación, te guiaré en los pasos para establecer inicialmente tu entorno:

Generar una lista de números aleatorios: Utiliza el módulo random para obtener una lista de números enteros aleatorios.
```
import random

data = [random.randint(0, 100) for _ in range(10)]
```
Ordenar la lista: La búsqueda binaria requiere una lista ordenada. Usa el método sort() para modificar la lista en lugar de sorted(), que devuelve una nueva lista.
```
data.sort()
print(data)
```

¿Cómo diseñar la interfaz de la función de búsqueda binaria?

Antes de escribir la lógica interna de nuestra función, debemos definir su estructura externa. La interfaz de nuestra función es crucial para que sea clara y funcional:

Nombre de la función: binary_search.
Parámetros requeridos: data (lista ordenada), target (número a buscar), low (índice bajo), high (índice alto).

Ejemplo de llamada a la función:

result = binary_search(data, target, 0, len(data) - 1)

¿Cómo implementar la búsqueda binaria usando recursión?

La recursión es clave para implementar una búsqueda binaria de manera eficiente. Te mostraré cómo hacerlo paso a paso:

Condición de parada: Si low es mayor que high, el elemento no está en la lista.
```
if low > high:
    return False
```
Calcular el índice medio: Esto se hace sumando low y high y dividiendo por dos.
```
mid = (low + high) // 2
```

Casos de búsqueda:

Si target es igual al elemento en el índice medio, regresa True.
Si target es menor, busca en la mitad izquierda.
Si target es mayor, busca en la mitad derecha.

if target == data[mid]:
    return True
elif target < data[mid]:
    return binary_search(data, target, low, mid - 1)
else:
    return binary_search(data, target, mid + 1, high)

¿Cómo mejorar tus habilidades con el algoritmo?

Finalizar una implementación no es el fin del aprendizaje. Te animo a que profundices:

Reto práctico: Implementa la búsqueda binaria sin recursión usando bucles. Observa cómo difiere la lógica y cómo manipular los índices.
Prueba y depuración: Genera diferentes listas, prueba con números variopintos y depura problemas lógicos o errores de sintaxis.

¿Qué se espera al probar el algoritmo?

Prueba tu implementación ejecutando el script. A medida que generas listas aleatorias y buscas elementos específicos, obtendrás práctica invaluable. Por ejemplo:

$ python binary_search.py
[2, 5, 10, 12, 17, 24, 31, 41, 56, 72]
¿Qué número te gustaría encontrar? 10
True

Al practicar y resolver retos adicionales, como eliminar la recursión, te perfeccionarás en el arte de la búsqueda binaria. Sigue explorando, ajustando y aprendiendo. ¡El mundo de la programación está lleno de posibilidades y está al alcance de tus habilidades!

Robin Jaime Beltran Montijo

student•

import random

def binary_search(data, target, low, high):
    while low <= high:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1




if __name__ == '__main__':

    data = [random.randint(0, 100) for i in range(10)]
    data.sort()
    print(data)
    target = int(input('What number would you like to find?'))
    found = binary_search(data, target, 0, len(data)-1)
    if found == True:
        print('The number: {} is in the list'. format(target))
    else:
        print('The number: {} is not in the list'.format(target))```

Brayan Urbina

student•

Podrias solo dejar

if found:

Y te podrias ahorrar la igualdad ya que found es True

if found == True

cristian josue

student•

Iteratividad en lugar de REcursividad Sólo es necesario definir la función con 2 parámetros

def binary_search(data, target)
low = data[0]
high = data [len(data) - 1]

Ya que low y high se pueden calcular al comienzo de la iteración.

Mauro Andrés Rocca Fontora

student•

Hola comunidad, les comento que al hacer este ejercicio me pasó de estar por una hora sin entender por qué la siguiente función recursiva no me retornaba el resultado correcto. El resultado era “None”.
Luego al compararlo con el código del profesor, me di cuenta que faltaba el “return” en el elif y el else. Comparto esto para tenerlo en cuenta a la hora de hacer funciones recursivas

def find_number(numbers, search, low, high):
	if low > high:
		return False

	middle = (low + high) // 2	

	if numbers[middle] == search:
		return True
	elif numbers[middle] > search:
		find_number(numbers, search, low, (middle - 1))
	else:
		find_number(numbers, search, (middle + 1), high)

Manuel Alejandro Aguilar Téllez Girón

student•

Había tenido el mismo problema, es la primera vez que veo funciones repulsivas

Aaron Joel Limachi Quispe

student•

Son funciones recursivas, no repulsivas A modo de chiste para principiantes estuvo genial 😂🤣

Alex John Chamba Macas

student•

Comparto mi solución iterativa a la búsqueda binaria

def binary_search_iterative(data, target, low, high):	
	while low<=high:
	    mid = (low + high)//2
	    if data[mid] == target:
	        return True
	    else:
	        if target < data[mid]:
	            high = mid-1
	        else:
	            low = mid+1
	
	return False

Royer Guerrero Pinilla

student•

Aquí esta mi aporte si no entienden lo de Binary Search lo que tienen que hacer es

Establecer "L" a 0 y "H" a la longitud del array - 1 (n - 1)
si "L" > "R", significa que debemos retornar False
Establecer "m" como la mitad de (L + R) / 2 la división debe ser entera (sin decimales)
Si Data[m] < Target, ahora L es igual a m + 1 y debemos volver al paso 2
Si Data[m] > Target, ahora H es igual a m - 1 y debemos volver al paso 2
Ahora si Target = Data[m] retornamos True

import random

def binary_search(data, target, low, high):
    
    while low <= high:
        
        if low > high:
            return False

        mid = (low + high) // 2

        if target == data[mid]:
            return True
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            

    return False

if __name__ == '__main__':
    data = [random.randint(1, 100) for i in range(10)]
    data.sort()
    print(data)

    target = int(input('Ingresa el número a adivinar? '))

    found = binary_search(data, target, 0, len(data) - 1)

    print(found)

Jesus Espino

student•

def f(data,target):
  lo = 0
  hi = len(data)
  while hi - lo > 1:
    mid = (lo + hi) // 2
    if data[mid] > target: hi = mid
    else: lo = mid
  return data[lo] == target

Aaron Joel Limachi Quispe

student•

Gracias por el código, está super claro.👍 Y creo que de todos los que revisé es el único que utiliza la idea de delimitar bien los límites superior e inferior.

Carmen Sánchez Salgado

student•

Muestra que hay mil formas de resolver un problema... bien!

Miguel Angel Ramirez Samano

student•

def bin_search(data, target, low, high):
    found = True
    while(found==True):
        mid = (low + high) // 2 
        if low > high:
            return False
        elif target == data[mid]:
            found = False
            return True
        elif target < data[mid]:
            high = mid -1
        else:
            low = mid + 1```

Francisco Garcia [C6]

student•

Solución con un for

import random

def loop_search(target, data):
    found = False
    
    for i in data:
        if i == target:
            found = True

    return found


if __name__ == '__main__':
    data = [random.randint(0, 100) for i in range(20)]
    data.sort()
    print(data)

    target = int(input('What number would you like to find? '))

    found = loop_search(target, data)

    print(found)

Omar Daniel Centeno

student•

Yeah, give me for! 🖐🏽

Marco Antonio Baquero Torres

student•

Tu codigo funciona, el problema es cuenado se tengan colecciones de datos muy vastas ya que estas recorriendo toda la lista hasta que encuentras el numero, yo creo que la idea tambies es optimizar la busqueda para hacerla mas rapida, de alli surge la idea de usar una solucion binaria, partiendo la lista por mitades cada vez, asi se acelera.

Roger Christian Cansaya Olazabal

student•

Reto:

import random

def binary_search(data,target): # low_idx indice y high_idx indice mayor de la lista
    low_idx = 0
    high_idx= len(data)-1
    solve = False
    while  low_idx <= high_idx:
        mid = (low_idx + high_idx)//2
        if target == data[mid]:
            solve = True
            break
        else:
            if target < data[mid]:
                high_idx = mid -1
            elif target > data[mid]:
                low_idx = mid + 1
    return solve

if __name__ =='__main__':

    data = [random.randint(0,10) for _ in range(10)]
    data.sort()
    print(data)
    target = int(input('What number would you like to find? '))
    found = binary_search(data,target)
    print(found)

Yorlys Oropeza

student•

Mi solución, solo un detalle tenía y es que en ciertas ocasiones enviaba False a pesar de estar el elemento, pero solo es colocar mayor o igual o menor igual(depende de como se realice) y se soluciona el problema

import random


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


def binary_search_with_while(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target >= data[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return False


if __name__ == '__main__':
    data = [random.randint(0,100) for i in range(10)]
    
    data.sort()
    
    print(data)
    
    target = int(input("What number would you like to find? "))
    #found = binary_search(data, target, 0, len(data) - 1)
    found = binary_search_with_while(data, target)
    
    print(found, target)```

Jonathan Osorio

student•

Reto:

from random import randint

def binary_search(list: list, objective: int, start: int, final: int):
    sorted_list = sorted(list)    

    while start <= final:
        mid = (start + final) // 2
        if objective > sorted_list[mid]:
            start = mid + 1
        elif objective < sorted_list[mid]:
            final = mid - 1
        elif objective == sorted_list[mid]:
            return 1
    else:
        return 0

if __name__ == '__main__':
    #test example
    list = [randint(0,20) for _ in range(0, 10)]
    print(bool(binary_search(list, 15, 0, len(list))))

Michelle Verano

student•

Que hermosa es la recurtion

Dennis Alejandro Salinas Estrada

student•

Asi me quedo a mi :)

Omar Daniel Centeno

student•

¿Creo que el último return usr está un poco raro no? En caso de que no lo encontrara o algo fallara, de todas maneras te devolvería el número. Podrías diferenciar lo que retorna cada return para poder diferenciar el resultado. . Espero explicarme. Saludos!

Manuel Alejandro Aguilar Téllez Girón

student•

Este es mi código del reto, agradezco a toda la comunidad porque me apoyé del código de todos y no me acuerdo de quién lo tomé exactamente xD. (Sí, al final lo hice yo solo, aunque sí me ayudaron).

import random

def binarySearch(d, t, s, e):
    x = False
    m = 0

    if s > e:
        x = False

    while s <= e:
        m = (s + e) // 2

        if t == d[m]:
            x = True
            return m
            break
        elif t < d[m]:
            e = m - 1
        else:
            s = m + 1

    return x



if __name__ == '__main__':
    """data = [random.randint(0, 100) for i in range(10)]"""
    d = []

    for i in range(10):
        d.append(random.randint(0, 100))

    d.sort()
    print(d)

    t = int(input("Number: "))
    found = binarySearch(d, t, 0, len(d) - 1)
    print("{} number is at {} position".format(t, found))

Carmen Sánchez Salgado

student•

hi comunidad, aquí mi solución!

<

def binary_search(data, target):
    low, hight = 0, len(data) -1

    while low <= hight:
        mid = (low + hight) // 2

        if target == data[mid]:
            return True
            break
        elif target < data[mid]:
            hight = mid -1
        else:
            low = mid +1

    return False

>

Carlos Centeno

student•

Mi solucion:

import random

def binary_search(data, target, low, higth):
    mid = (low + higth) // 2
    #print(mid)
    ok = True

    while ok:
        if low > higth:
            ok = False
            return False

        if target == data[mid]:
            ok = False
            return True
        elif target < data[mid]:
            higth = mid - 1
        else:
            low = mid + 1        
        mid = (low + higth) // 2
        #print(mid)

    return False

if __name__ == '__main__':
    data = [random.randint(0, 100) for i in range(10)]
    data.sort()
    print(data)

    target = int(input('What number would you like to find? '))
    found = binary_search(data, target, 0, len(data) - 1)
    print(found)

Osvaldo Trejo

student•

def binary_search_without_recursion(data, target, low, high):
    while low <= high:
        mid = (low + high) // 2

        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else :
            low = mid + 1 
    return False

JoséAngel Sánchez

student•

Encontré este algoritmo un poco más sencillo de ver, por si a alguien le funciona.

def busquedaBinaria(unaLista, item):
	    primero = 0
	    ultimo = len(unaLista)-1
	    encontrado = False
	
	    while primero<=ultimo and not encontrado:
	        puntoMedio = (primero + ultimo)//2
	        if unaLista[puntoMedio] == item:
	            encontrado = True
	        else:
	            if item < unaLista[puntoMedio]:
	                ultimo = puntoMedio-1
	            else:
	                primero = puntoMedio+1
	
	    return encontrado

Carmen Sánchez Salgado

student•

La desventaja que veo es que, continua con el ciclo a pesar de que ya encontró el valor buscado.

Saludos! = )

Fabrizio Fasanando Sotelo

student•

Esta es mi solución usando loops, como la ven?

import random


def binary_search(number_list):
    found = False
    low, high = 0, len(number_list) - 1
    mid = (low + high) // 2
    target = int(input('What number would you like to find?: '))

    while not found:
        if mid <= low or mid >= high:
            print('El número NO se encuentra en la lista.')
            break
        if target == number_list[mid]:
            found = True
        elif target < number_list[mid]:
            mid = (low + mid - 1) // 2
        elif target > number_list[mid]:
            mid = (mid + high + 1) // 2

    if found:
        print('El número si se encuentra en la lista.')


if __name__ == '__main__':
    number_list = [random.randint(1, 21) for i in range(21)]
    number_list.sort()
    print(number_list)
    binary_search(number_list)

Luis Arturo Huerta Rodríguez

student•

Qué tal Fabrizio19! Buena idea de cambiar la manera de hacer la búsqueda con un while loop en lugar del if que se utilizó en el curso. A lo rápido encuentro no necesario el primer if dentro del while loop. Si tomaste el punto medio entre low y high, no es necesario comparar si está debajo o arriba del low y high respectivamente, siendo mid un promedio, nunca podrá estar abajo o arriba de los valores que le dieron origen. Saludos!

Hector F

student•

Mi solución al reto:

import random


def binarySearch(data, target):
    data = sorted(data)
    min, max = 0, len(data) - 1

    while min <= max:
        actual_index = (min + max) // 2

        if target == data[actual_index]:
            return True
        elif target < data[actual_index]:
            max = actual_index - 1
        else:
            min = actual_index + 1
    return False


if __name__ == '__main__':
    random_numbers = [random.randint(0, 100) for i in range(20)]

    print(random_numbers)

    found = binarySearch(random_numbers, int(input('What number would you like to found? ')))

    print(found)

Nicolás Mayorga Vargas

student•

Gran solución. Felicidades

Hector F

student•

Muchas gracias @nicolas-mayorga-vargas!! ¿Ya intentaste el reto?

Pablo Perez

student•

<code>
import random



def binary_search(n_list, obj, low, high):
    if low > high:
        return False

    for n in n_list:
        mid = (low + high) // 2
        if obj == n_list[mid]:
            return True

        elif obj < n_list[mid]:
            high = mid - 1 
            
        else:
            low = mid + 1
            
    


if __name__ == "__main__":
    n_list = [random.randint(0,100) for n in range(20)]
    n_list.sort()

    print(n_list)

    obj = int(input('Number to find: '))

    found = binary_search(n_list, obj, 0, len(n_list)-1)
    
    if found:
        print(f'I Found the number {obj}!')

    else:
        print(f'I don\'t found the number {obj}')