Mantener una lista ordenada parece sencillo: añade el nuevo elemento y llama a sort(). Este enfoque funciona con colecciones pequeñas o cambios poco frecuentes, pero repite trabajo cuando los valores llegan continuamente y la aplicación necesita consultar rangos, límites, vecinos o posiciones de inserción. bisect en Python resuelve este escenario mediante búsqueda binaria. El módulo localiza la posición correcta en una secuencia ya ordenada sin recorrer todos los elementos.
En esta guía aprenderás las diferencias entre bisect_left() y bisect_right(), cómo usar insort(), cómo buscar registros con key, cuándo precalcular claves y cuáles son los límites reales de rendimiento. El tema complementa los artículos sobre sort y sorted en Python, listas en Python, funciones en Python, el módulo collections y las recomendaciones para mejorar scripts lentos.
Qué es el módulo bisect
El módulo bisect implementa un algoritmo de bisección para localizar posiciones dentro de listas ordenadas. En lugar de comparar el objetivo con todos los valores, la búsqueda revisa el centro del intervalo actual, descarta la mitad de las posiciones posibles y repite el proceso. Encontrar un punto de inserción cuesta por ello O(log n).
La documentación oficial de bisect destaca que estas funciones buscan posiciones de inserción. No llaman a __eq__() para decidir si el valor existe; utilizan comparaciones de orden y devuelven un índice entre los elementos. Este comportamiento resulta útil para inserciones, límites, vecinos y consultas por intervalo.
La lista debe estar ordenada
La condición más importante es que la secuencia ya esté ordenada según el mismo criterio utilizado por la búsqueda. Si la lista está desordenada, el índice devuelto será un entero válido, pero no tendrá un significado fiable.
from bisect import bisect_left
numeros = [3, 8, 12, 19, 25]
indice = bisect_left(numeros, 15)
print(indice) # 3
print(numeros[:indice])
print(numeros[indice:])El resultado indica que 15 debería insertarse antes de 19, en el índice 3. La función no modifica la lista; solamente calcula la posición.
bisect_left y bisect_right
La diferencia aparece cuando ya existen valores iguales. bisect_left() devuelve la posición anterior al primer elemento igual. bisect_right(), disponible también mediante el alias bisect(), devuelve la posición posterior al último elemento igual.
from bisect import bisect_left, bisect_right
valores = [10, 20, 20, 20, 30]
inicio = bisect_left(valores, 20)
fin = bisect_right(valores, 20)
print(inicio) # 1
print(fin) # 4
print(valores[inicio:fin])La combinación permite localizar rápidamente todo el intervalo ocupado por duplicados. La cantidad de apariciones es fin - inicio. El mismo patrón sirve para fechas, precios, puntuaciones, versiones y cualquier clave ordenable.
Buscar un valor exacto
Como bisect_left() devuelve un punto de inserción incluso cuando el objetivo no existe, debes comprobar el elemento de esa posición antes de considerar que la búsqueda tuvo éxito.
from bisect import bisect_left
def encontrar_indice(valores, objetivo):
indice = bisect_left(valores, objetivo)
if indice != len(valores) and valores[indice] == objetivo:
return indice
raise ValueError(f"{objetivo!r} no encontrado")
print(encontrar_indice([2, 5, 9, 14], 9))Para muchas búsquedas exactas, un diccionario o un conjunto suele ser más adecuado. bisect destaca cuando el orden es importante y necesitas límites, vecinos o posiciones dentro de una secuencia.
Insertar con insort
insort_left() e insort_right() combinan la búsqueda de la posición con list.insert(). La versión izquierda coloca el nuevo elemento antes de los iguales; la versión derecha lo coloca después.
from bisect import insort
cola = [4, 9, 15, 22]
insort(cola, 12)
insort(cola, 9)
print(cola)Usar append() rompería el orden cuando el valor nuevo no fuera mayor que el último. Ordenar toda la lista después de cada inserción también funcionaría, aunque repetiría comparaciones que la búsqueda binaria puede evitar.
El coste real de insertar
La búsqueda binaria cuesta O(log n), pero insertar en el centro de una lista cuesta O(n), porque las referencias posteriores deben desplazarse. Por tanto, insort() es cómodo para muchas consultas y un volumen moderado de inserciones, pero no convierte una lista en una estructura con inserción logarítmica.
Cuando existen millones de actualizaciones aleatorias, considera un árbol equilibrado, una base de datos indexada o una biblioteca especializada en colecciones ordenadas. Si los valores llegan en orden creciente, append() sigue siendo la solución más sencilla y rápida. El tutorial oficial de estructuras de datos aporta contexto adicional sobre listas, colas, diccionarios y conjuntos.
Limitar la búsqueda con lo y hi
Los parámetros lo y hi restringen la búsqueda a una parte de la secuencia. Son útiles cuando otra operación ya ha delimitado la región relevante.
from bisect import bisect_left
datos = [2, 5, 8, 11, 14, 17, 20]
indice = bisect_left(datos, 13, lo=2, hi=6)
print(indice)Los límites siguen la convención de los slices: lo está incluido y hi está excluido. La región elegida debe conservar el mismo criterio de ordenación.
Buscar objetos con key
Desde Python 3.10, las funciones aceptan el argumento key. Esta función extrae la clave de comparación de cada registro almacenado. Durante una búsqueda, key no se aplica al valor x; el programa proporciona directamente la clave buscada.
from bisect import bisect_left
from operator import itemgetter
productos = [
{"nombre": "Cuaderno", "precio": 18.0},
{"nombre": "Ratón", "precio": 65.0},
{"nombre": "Teclado", "precio": 120.0},
]
por_precio = itemgetter("precio")
indice = bisect_left(productos, 70.0, key=por_precio)
print(productos[indice]["nombre"])Los registros deben estar ordenados con la misma función key. Ordenar por nombre y buscar por precio rompe el contrato de la búsqueda binaria, aunque el código no genere una excepción.
Insertar registros con key
En las funciones insort, la clave se aplica al elemento nuevo durante la búsqueda, mientras que el objeto completo se inserta en la lista.
from bisect import insort
from operator import itemgetter
tareas = [
{"prioridad": 1, "titulo": "Restaurar servicio"},
{"prioridad": 3, "titulo": "Generar informe"},
]
nueva = {"prioridad": 2, "titulo": "Responder al cliente"}
insort(tareas, nueva, key=itemgetter("prioridad"))
print([tarea["prioridad"] for tarea in tareas])Cuando existen prioridades iguales, elige conscientemente entre inserción izquierda y derecha. Para preservar el orden de llegada, añade un contador creciente al registro o a la clave de comparación.
Precalcular claves
Las funciones de búsqueda no conservan los resultados de key. En un bucle, una función costosa puede ejecutarse muchas veces sobre los mismos registros. Una solución consiste en mantener una lista paralela con claves precalculadas.
from bisect import bisect_left
clientes = [
("Ana", 1200),
("Bruno", 2500),
("Carla", 4100),
]
saldos = [cliente[1] for cliente in clientes]
indice = bisect_left(saldos, 3000)
print(clientes[indice])Al insertar o eliminar registros, actualiza ambas listas como una sola operación lógica. Otra alternativa indicada por la documentación es aplicar functools.cache() cuando la función de clave sea pura y reutilice los mismos argumentos.
Consultas por rango
Una aplicación habitual consiste en seleccionar todos los valores entre dos límites inclusivos. Usa bisect_left() para el límite inferior y bisect_right() para el superior.
from bisect import bisect_left, bisect_right
temperaturas = [12, 15, 18, 18, 21, 24, 27, 30]
inicio = bisect_left(temperaturas, 18)
fin = bisect_right(temperaturas, 24)
print(temperaturas[inicio:fin])Localizar ambos límites cuesta O(log n). Crear el slice cuesta tiempo y memoria proporcionales a la cantidad de elementos devueltos. Cuando solo necesitas contar, calcula fin - inicio y evita copiar datos.
Clasificar valores por intervalos
bisect() también puede transformar umbrales ordenados en categorías. El índice devuelto selecciona el grupo correspondiente.
from bisect import bisect
limites = [60, 70, 80, 90]
calificaciones = "FDCBA"
def calificacion(nota):
return calificaciones[bisect(limites, nota)]
print(calificacion(77))
print(calificacion(90))El patrón sirve para tramos fiscales, niveles de riesgo, tamaños de paquetes, precios escalonados y acuerdos de servicio. Documenta si cada límite pertenece al intervalo anterior o al siguiente, porque esa decisión determina el uso de bisección izquierda o derecha.
Encontrar valores vecinos
El índice de inserción permite obtener los valores más cercanos alrededor del objetivo. Después de bisect_left(valores, x), el elemento en indice - 1 es el mayor valor inferior a x, cuando existe. El elemento del propio índice es el primero mayor o igual.
from bisect import bisect_left
horarios = [8, 10, 13, 16, 19]
indice = bisect_left(horarios, 14)
anterior = horarios[indice - 1] if indice else None
siguiente = horarios[indice] if indice != len(horarios) else None
print(anterior, siguiente)Esta técnica es útil para calendarios, series temporales, versiones de software, sensores y puntos de precio.
Crear funciones de consulta reutilizables
El código resulta más claro cuando las reglas de límites se encapsulan en funciones con nombres explícitos. Una función puede devolver el primer valor mayor o igual, mientras otra devuelve el último valor menor.
from bisect import bisect_left
def encontrar_mayor_igual(valores, objetivo):
indice = bisect_left(valores, objetivo)
if indice != len(valores):
return valores[indice]
raise ValueError("no existe un valor suficiente")
def encontrar_menor(valores, objetivo):
indice = bisect_left(valores, objetivo)
if indice:
return valores[indice - 1]
raise ValueError("no existe un valor menor")Los nombres claros reducen errores de una posición y hacen visibles las decisiones sobre límites inclusivos o exclusivos.
bisect, diccionario, set o heap
Usa bisect cuando el orden importe y necesites rangos, vecinos o posiciones de inserción. Usa diccionario o set para búsquedas exactas frecuentes. Usa heapq cuando la operación principal sea retirar repetidamente el elemento menor o mayor, sin necesidad de buscar posiciones arbitrarias.
Una base de datos indexada es más apropiada cuando los datos no caben en memoria, necesitan persistencia o reciben actualizaciones concurrentes. La elección depende del patrón completo de lecturas y escrituras, no solamente de la complejidad de una búsqueda.
Seguridad con múltiples hilos
Las funciones de bisect no son seguras cuando varios hilos operan sobre la misma secuencia. Si un hilo modifica la lista mientras otro busca o inserta, el orden puede corromperse y el comportamiento queda indefinido. Protege la operación completa con un bloqueo o utiliza estructuras separadas.
No es suficiente bloquear únicamente la llamada a bisect() y liberar antes de insert(). Otro hilo podría cambiar la colección entre ambos pasos. El cálculo de la posición y la inserción deben formar una única sección crítica.
Errores frecuentes
- Aplicar bisect a una lista desordenada.
- Ordenar los registros con una clave y buscar con otra.
- Interpretar el índice como prueba de que el valor existe.
- Ignorar la diferencia entre inserción izquierda y derecha.
- Esperar inserciones
O(log n)en una lista normal. - Recalcular una función
keycostosa en miles de búsquedas. - Modificar la misma lista desde varios hilos sin sincronización.
Cómo probar las búsquedas
Prueba los extremos: lista vacía, valor menor que todos, mayor que todos, duplicados y límites exactos. Confirma también que una secuencia de inserciones mantiene la ordenación.
from bisect import insort
def test_inserciones_mantienen_orden():
valores = []
for numero in [9, 2, 7, 7, 1]:
insort(valores, numero)
assert valores == [1, 2, 7, 7, 9]Las funciones de rango deben incluir casos sin resultados, un único resultado, límites duplicados y todos los elementos dentro del intervalo. Estas pruebas detectan rápidamente errores de índices.
Buenas prácticas
- Centraliza búsquedas e inserciones en funciones pequeñas.
- Documenta el criterio de ordenación y la política de duplicados.
- Utiliza una función
keycoherente con la ordenación inicial. - Precalcula claves cuando la extracción sea costosa.
- Evita crear slices cuando solo necesites contar.
- Mide las inserciones grandes antes de elegir una lista.
- Protege la operación completa cuando exista concurrencia.
Conclusión
bisect en Python convierte las listas ordenadas en estructuras eficientes para localizar puntos de inserción, límites y valores vecinos. bisect_left y bisect_right definen el tratamiento de duplicados, mientras que insort conserva el orden después de nuevas entradas. El argumento key extiende la técnica a tuplas, diccionarios y objetos personalizados.
La búsqueda es logarítmica, pero la inserción en una lista continúa siendo lineal. Por ello, el módulo funciona especialmente bien en procesos con muchas lecturas y una cantidad moderada de cambios. Cuando aumentan la escala, la concurrencia o la necesidad de persistencia, otra estructura puede ser más adecuada. Con un contrato de ordenación documentado y buenas pruebas de límites, bisect ofrece una solución sencilla, predecible y potente.
