bisect — Algoritmo de bisección de arreglos

Código fuente: Lib/bisect.py

Este módulo brinda soporte para mantener una lista ordenada sin tener que reordenar la lista tras cada nueva inserción. Para listas largas de elementos que tienen operaciones de comparación costosas, será una mejora respecto a la estrategia más habitual. El módulo se llama bisect porque usa un algoritmo de bisección básico para lograr su objetivo. El código fuente puede ser útil como ejemplo del algoritmo en funcionamiento (¡las precondiciones ya están bien de antemano!).

Las siguientes funciones están disponibles:

bisect.bisect_left(a, x, lo=0, hi=len(a))

Ubicar el punto de inserción para x en a para mantener el ordenamiento. Los parámetros lo (inferior) y hi (superior) pueden utilizarse para especificar un subconjunto (subset) de la lista que debería considerarse. Por defecto, se utiliza la lista completa. Si x ya está presente en a, el punto de inserción será antes (a la izquierda de) cualquier elemento existente. El valor de retorno es adecuado para que se utilice como primer parámetro para list.insert(), suponiendo que a ya está ordenada.

El punto de inserción retornado i particiona al arreglo a en dos mitades, tal que all(val < x for val in a[lo:i]) para el lado izquierdo y all(val >= x for val in a[i:hi]) para el derecho.

bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))

Similar a bisect_left(), pero retorna un punto de inserción que viene después (a la derecha de) cualquier entrada de x en a.

El punto de inserción retornado i particiona al arreglo a en dos mitades, tal que all(val <= x for val in a[lo:i]) para el lado izquierdo y all(val > x for val in a[i:hi]) para el derecho.

bisect.insort_left(a, x, lo=0, hi=len(a))

Inserta x en a de forma ordenada. Esto equivale a a.insert(bisect.bisect_left(a, x, lo, hi), x), suponiendo que a ya está ordenada. Tenga presente que la búsqueda O(log n) está dominada por el paso de inserción O(n) lento.

bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))

Similar a insort_left(), pero inserta x en a después de cualquier entrada x existente.

Ver también

Receta SortedCollection que usa bisección para construir una «clase-colección» con todas las funcionalidades, con métodos de búsqueda directos y con soporte para una función-clave (key-function). Las claves son procesadas de antemano, para ahorrar llamadas innecesarias a la función clave durante las búsquedas.

Búsqueda en listas ordenadas

Las funciones anteriores bisect() son útiles para encontrar puntos de inserción, pero pueden resultar difíciles o engorrosas para tareas de búsqueda habituales. Las cinco funciones que siguen muestran cómo convertirlas en búsquedas estándar para listas ordenadas:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

Otros ejemplos

La función bisect() puede ser útil para búsquedas en tablas numéricas. Este ejemplo utiliza bisect() para buscar una calificación de un examen dada por una letra, basada en un conjunto de marcas numéricas ordenadas: 90 o más es una “A”, de 80 a 89 es una “B”, y así sucesivamente:

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

A diferencia de la función sorted(), no tiene sentido para las funciones bisect() tener los argumentos key o reversed, porque conduciría a un diseño ineficiente (llamadas sucesivas a funciones de bisección no «recordarían» todas las búsquedas previas con clave).

En su lugar, es mejor buscar en una lista de claves procesadas de antemano para encontrar el índice del registro en cuestión:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)