Trabajar con listas ordenadas a veces puede ser un poco complicado. Debe mantener el orden de la lista después de cada inserción y buscar elementos dentro de ella de manera eficiente. La búsqueda binaria es un potente algoritmo para buscar en una lista ordenada. Si bien implementarlo desde cero no es demasiado difícil, puede llevar mucho tiempo. Afortunadamente, Python ofrece el módulo bisect, que facilita mucho el manejo de listas ordenadas.

¿Qué es la búsqueda binaria?

La búsqueda binaria es un algoritmo que encuentra la posición de un valor objetivo dentro de una matriz ordenada. Imagine que está buscando un nombre en una guía telefónica. En lugar de comenzar desde la primera página, probablemente comience en la mitad del libro y decida si continúa buscando en la primera o segunda mitad, según si el nombre es alfabéticamente mayor o menor que el del medio. La búsqueda binaria funciona de manera similar: comienza con dos punteros, uno al principio y otro al final de la lista. Luego se calcula el elemento intermedio y se compara con el objetivo.

El módulo bisect: simplificación de operaciones de listas ordenadas

Si bien la búsqueda binaria es efectiva, escribir la implementación cada vez puede resultar tedioso. Pero ¿y si pudieras realizar las mismas operaciones con una sola línea de código? Ahí es donde entra en juego el módulo bisect de Python. Como parte de la biblioteca estándar de Python, bisect le ayuda a mantener una lista ordenada sin necesidad de ordenarla después de cada inserción. Lo hace utilizando un algoritmo de bisección simple.

El módulo de bisección proporciona dos funciones clave: bisectar y ordenar. La función bisect encuentra el índice donde se debe insertar un elemento para mantener la lista ordenada, mientras que insort inserta el elemento en la lista manteniendo su orden.

Uso del módulo bisect: un ejemplo práctico

Comencemos importando el módulo:

import bisect

Ejemplo 1: insertar un número en una lista ordenada

Supongamos que tenemos una lista ordenada de números:

data = [1, 3, 5, 6, 8]

Para insertar un nuevo número manteniendo la lista ordenada, simplemente use:

bisect.insort(data, 7)

después de ejecutar este código, los datos se verán así:

[1, 3, 5, 6, 7, 8]

Ejemplo 2: encontrar el punto de inserción

¿Qué pasa si solo quieres saber dónde se insertaría un número sin insertarlo realmente? Puedes usar las funciones bisect_left o bisect_right:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Esto nos dice que el número 4 debe insertarse en el índice 2 para mantener la lista ordenada.

Ejemplo 3: mantener el orden en una lista dinámica

Supongamos que está administrando una lista que crece dinámicamente y necesita insertar elementos mientras se asegura de que permanezca ordenada:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Esto generará la lista en cada paso a medida que se insertan elementos:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Ejemplo 4: uso de bisect con objetos personalizados

Supongamos que tiene una lista de objetos personalizados, como tuplas, y desea insertarlos según un criterio específico:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

O quizás quieras insertar en función del segundo elemento de cada tupla:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect en acción: buscando palabras

El módulo de bisección no se limita a números; también puede resultar útil para buscar en listas de cadenas, tuplas, caracteres, etc.
Por ejemplo, para buscar una palabra en una lista ordenada:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

O para buscar la primera palabra en un grupo de palabras con un prefijo específico:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Sin embargo, tenga en cuenta que bisect_left devuelve el índice donde se debe insertar el objetivo, no si el objetivo existe en la lista.

Variantes de bisect y insort

El módulo también incluye variantes del lado derecho: bisect_right e insort_right. Estas funciones devuelven el índice más a la derecha en el que insertar un elemento si ya está en la lista. Por ejemplo, bisect_right devolverá el índice del primer elemento mayor que el objetivo si el objetivo está en la lista, mientras que insort_right inserta el elemento en esa posición.

bisectar bajo el capó

El poder del módulo bisect radica en su implementación eficiente del algoritmo de búsqueda binaria. Cuando llamas a bisect.bisect_left, por ejemplo, la función esencialmente realiza una búsqueda binaria en la lista para determinar el punto de inserción correcto para el nuevo elemento.

Así es como funciona bajo el capó:

1. Inicialización: la función comienza con dos punteros, bajo y alto, que representan los límites inferior y superior del rango de búsqueda dentro de la lista. Inicialmente, lo se establece al inicio de la lista (índice 0) y hi se establece al final de la lista (índice igual a la longitud de la lista). Pero también puedes especificar valores bajos y altos personalizados para buscar dentro de un rango específico de la lista.

2. Bisección: dentro de un bucle, la función calcula el punto medio (mid) entre lo y hi. Luego compara el valor medio con el valor objetivo que desea insertar.

3. Comparación:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. Terminación: este proceso continúa, reduciendo a la mitad el rango de búsqueda cada vez, hasta que lo sea igual a hi. En este punto, lo (o hi) representa el índice correcto donde se debe insertar el objetivo para mantener el orden de la lista.

2. Inserción: para la función ordenar, una vez que se encuentra el índice correcto usando bisect_left, el objetivo se inserta en la lista en esa posición.

Este enfoque garantiza que el proceso de inserción sea eficiente, con una complejidad temporal de O(log n) para la búsqueda y O(n) para la inserción debido a la operación de cambio de lista. Esto es significativamente más eficiente que ordenar la lista después de cada inserción, especialmente para conjuntos de datos grandes.

ejemplo de código bisect_left:

    if lo 



ejemplo de código insort_left:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  Conclusión


El módulo bisect hace que trabajar con listas ordenadas sea sencillo y eficiente. La próxima vez que necesite realizar una búsqueda binaria o insertar elementos en una lista ordenada, recuerde el módulo bisect y ahorre tiempo y esfuerzo.