El módulo bisect usa búsqueda binaria para localizar posiciones en listas ordenadas. Permite encontrar el punto de inserción sin recorrer todos los elementos y ofrece insort() para conservar el orden después de incluir un valor. Es útil en índices en memoria, rangos, rankings, calendarios y algoritmos que reciben datos gradualmente.
La búsqueda cuesta O(log n), pero insertar en una lista sigue costando O(n), porque las referencias posteriores deben desplazarse. bisect funciona mejor cuando las consultas son frecuentes y las inserciones moderadas. Para muchas actualizaciones, puede ser mejor una base de datos o una estructura especializada.
La lista debe estar ordenada
Las funciones no verifican esta condición.
from bisect import bisect_left
valores = [10, 20, 30, 40]
posicion = bisect_left(valores, 25)
print(posicion)
Si la secuencia usa otra regla o está desordenada, el resultado no es fiable.
bisect_left
bisect_left() devuelve la posición anterior a valores iguales.
valores = [10, 20, 20, 20, 30]
print(bisect_left(valores, 20))
Sirve para encontrar la primera ocurrencia o insertar antes de duplicados.
bisect_right
bisect_right(), también disponible como bisect(), devuelve la posición posterior a valores iguales.
from bisect import bisect_right
print(bisect_right(valores, 20))
Úsalo cuando los nuevos elementos iguales deban quedar después.
Localiza duplicados
Las dos posiciones delimitan todos los elementos iguales.
inicio = bisect_left(valores, objetivo)
fin = bisect_right(valores, objetivo)
iguales = valores[inicio:fin]
El slice copia referencias. Conserva los índices si no necesitas la copia.
insort_left e insort_right
Estas funciones localizan la posición e insertan el valor.
from bisect import insort_left
insort_left(valores, 25)
La búsqueda es logarítmica, pero mover elementos sigue siendo lineal.
No ordenes tras cada append
insort() evita ordenar toda la lista después de cada elemento.
Si ya tienes muchos valores nuevos, normalmente conviene extender y ordenar una sola vez.
Búsqueda exacta
bisect devuelve posiciones, no una función de match exacto.
def indice_exacto(items, valor):
indice = bisect_left(items, valor)
if indice != len(items) and items[indice] == valor:
return indice
raise ValueError("valor no encontrado")
Comprueba el límite antes de acceder.
Encuentra el valor inferior
def menor_que(items, valor):
indice = bisect_left(items, valor)
if indice:
return items[indice - 1]
raise ValueError("no existe un valor menor")
Variantes similares encuentran menor o igual, mayor o igual y mayor estricto.
Clasifica rangos
Una lista de límites puede mapear números a etiquetas.
limites = [0, 10, 20, 50]
etiquetas = ["negativo", "bajo", "medio", "alto", "muy alto"]
clase = etiquetas[bisect_right(limites, numero)]
Prueba valores exactamente en los límites para confirmar la política.
Parámetro key
Las versiones modernas permiten una función key para los elementos existentes.
registros = [
{"id": 1, "nombre": "A"},
{"id": 5, "nombre": "B"},
]
posicion = bisect_left(registros, 3, key=lambda item: item["id"])
El valor buscado se compara con las claves; no pasa automáticamente por la misma función.
Cachea claves costosas
Una key cara puede ejecutarse varias veces durante la búsqueda.
Mantén una lista paralela de claves o utiliza cache con registros inmutables. Actualiza ambas secuencias de forma atómica.
ids = [item.id for item in registros]
posicion = bisect_left(ids, nuevo.id)
ids.insert(posicion, nuevo.id)
registros.insert(posicion, nuevo)
Claves compuestas con tuplas
Las tuplas usan orden lexicográfico.
eventos = [(10, 1, "a"), (10, 2, "b"), (20, 1, "c")]
posicion = bisect_right(eventos, (10, float("inf"), ""))
Evita payloads no comparables después de campos que pueden empatar. Usa una secuencia única.
Fechas y horas
Objetos datetime compatibles pueden ordenarse, pero mezclar valores aware y naive genera error.
Normaliza timezones y define el orden de timestamps iguales.
Rankings
En un ranking ascendente, bisect_left() ofrece la posición. Para orden descendente, usa claves negativas o una regla consistente.
Las actualizaciones muy frecuentes pueden volver costosa la inserción en lista.
Percentiles
Una lista ordenada permite consultar cuantiles por índice, pero guardar todas las observaciones puede consumir memoria.
Para streams grandes, considera algoritmos aproximados.
No modifiques durante la búsqueda
Las funciones no son seguras si otra thread cambia la secuencia al mismo tiempo.
Protege consulta e inserción con el mismo lock o utiliza snapshots inmutables.
Búsqueda e inserción atómicas
Calcular una posición e insertar después permite que otro writer invalide el índice.
with lock:
posicion = bisect_left(valores, nuevo)
valores.insert(posicion, nuevo)
insort() combina los pasos, pero el acceso compartido todavía necesita sincronización.
NaN y orden total
float('nan') tiene comparaciones especiales y no forma parte de un orden total normal.
Filtra o normaliza NaN antes de mantener una lista numérica ordenada.
Claves mutables
Si un campo usado para ordenar cambia después de insertar, la lista deja de estar ordenada.
Elimina y reinserta el registro o usa claves inmutables.
Complejidad real
La búsqueda hace pocas comparaciones, pero insertar desplaza referencias. En listas grandes ese movimiento domina el coste.
Mide con la proporción real de lecturas y escrituras.
bisect frente a heapq
heapq es mejor para retirar repetidamente el mínimo. bisect es mejor para acceso por índice, rangos y vecinos.
Consulta heapq en Python.
bisect frente a set y dict
Para comprobar existencia, set y dict suelen ofrecer O(1) promedio.
Usa bisect cuando importen el orden, la posición o los intervalos.
Persistencia
Valida u ordena los datos al cargarlos. No confíes en que un archivo externo permanece ordenado.
Para índices enormes, una base de datos puede ser más apropiada.
Seguridad
Limita la cantidad de elementos externos. Una lista ordenada sin límite puede agotar memoria y ralentizar cada inserción.
Valida claves y evita comparadores con side effects.
Pruebas
Prueba lista vacía, un elemento, duplicados, límites, valores menores y mayores que todos, claves compuestas, NaN, actualizaciones y concurrencia.
Comprueba la invariante items == sorted(items) después de secuencias de operaciones.
Errores comunes
Los fallos frecuentes son usar una lista desordenada, confundir left y right, olvidar el coste lineal de insertar, cambiar claves en el lugar, usar key mal, ignorar NaN y separar búsqueda e inserción sin lock.
Conclusión
bisect ofrece búsqueda binaria e inserción ordenada con una API pequeña. Encaja en secuencias en memoria con muchas consultas y actualizaciones moderadas.
Elige left o right de forma deliberada, conserva una regla de orden y sincroniza cambios concurrentes. Consulta la documentación oficial de bisect y heapq en Python.
