Python Bisect - Búsqueda binaria

1. bisect.bisect_left() Descripción general
2. Aplicaciones de bisect_left()
3. bisect.bisect_right() Descripción general
4. Aplicaciones de bisect_right()

En este artículo, veremos cómo usar los módulos integrados de Python para realizar búsquedas binarias. El módulo bisect se basa en el método de bisección para encontrar las raíces de funciones. Consta de 6 funciones: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right() que nos permite encontrar el índice de un elemento o inserte el elemento en la posición correcta en una lista. También ayuda a mantener la lista ordenada después de cada inserción. Pero para que funcionen correctamente, debemos asegurarnos de que el array ya esté ordenada.

bisect.bisect_left() Descripción general

Se utiliza para ubicar el punto de inserción más a la izquierda de un número x dentro de una lista ordenada. Si x ya está presente en la lista, entonces se insertará una nueva x en la posición más a la izquierda entre todas las x de la lista.

Sintaxis

bisect_left(arr, x, lo=0, hi=len(a))

Parámetros

Retorna

Devuelve un punto de inserción que dividel array en dos mitades: la primera con todos los valores menores que x y la segunda con todos los valores mayores que x.

Aplicaciones de bisect_left()

Encuentra la primera aparición de un elemento

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1


a = [1, 2, 3, 3, 3]
x = int(3)
res = binary_search(a, x)
if res == -1:
    print("Element not Found")
else:
    print("First occurrence of", x, "is at index", res)

Producción :

First occurrence of 3 is at index 2

Encuentre el mayor valor menor que x

from bisect import bisect_left


def binary_search(a, x):
    i = bisect_left(a, x)
    if i:
        return i - 1
    else:
        return -1


# Driver code
a = [1, 2, 4, 4, 8]
x = int(7)
res = binary_search(a, x)
if res == -1:
    print("There is no value smaller than", x)
else:
    print("Largest value smaller than", x, " is at index", res)

Producción :

Largest value smaller than 7 is at index 3

bisect.bisect_right() Descripción general

Se utiliza para devolver el punto de inserción más a la derecha de un número x dentro de una lista ordenada. Si x ya está presente en la lista, entonces se insertará una nueva x en la posición más a la derecha entre todas las x de la lista.

Sintaxis

bisect_right(arr, x, lo=0, hi=len(a))

Parámetros

Retorna

Devuelve un punto de inserción que dividel array en dos mitades: la primera con todos los valores <= x y la segunda con todos los valores> x.

Aplicaciones de bisect_right()

Encuentra la última aparición de un elemento

from bisect import bisect_right


def binary_search(a, x):
    i = bisect_right(a, x)
    if i != len(a) + 1 and a[i - 1] == x:
        return i - 1
    else:
        return -1


a = [1, 2, 4, 4]
x = int(4)
res = binary_search(a, x)
if res == -1:
    print(x, "is absent")
else:
    print("Last occurrence of", x, "is present at", res)

Producción :

Last occurrence of 4 is present at 3