Búsqueda binaria (bisect) en Python

La búsqueda binaria es una técnica utilizada para buscar elementos en una lista ordenada. En este artículo, veremos las funciones de la biblioteca para realizar búsquedas binarias.
Encontrar la primera aparición de un elemento. 
 

bisect.bisect_left(a, x, lo=0, hi=len(a)) : Devuelve el punto de inserción más a la izquierda de x en una lista ordenada. Los dos últimos parámetros son opcionales, se utilizan para buscar en la sublista.

# Python code to demonstrate working
# of binary search in library
from bisect import bisect_left
 
def BinarySearch(a, x):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1
 
a  = [1, 2, 4, 4, 8]
x = int(4)
res = BinarySearch(a, x)
if res == -1:
    print(x, "is absent")
else:
    print("First occurrence of", x, "is present at", res)

First occurrence of 4 is present at 2

Encontrar el mayor valor menor que x. 
 

# Python code to demonstrate working
# of binary search in library
from bisect import bisect_left
 
def BinarySearch(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 = BinarySearch(a, x)
if res == -1:
    print("No value smaller than ", x)
else:
    print("Largest value smaller than ", x, " is at index ", res)

Largest value smaller than  7  is at index  3

Encontrar la ocurrencia más a la derecha
 

bisect.bisect_right(a, x, lo=0, hi=len(a)) Devuelve el punto de inserción más a la derecha de x en una lista ordenada a. Los dos últimos parámetros son opcionales, se utilizan para buscar en la sublista.

# Python code to demonstrate working
# of binary search in library
from bisect import bisect_right
 
def BinarySearch(a, x):
    i = bisect_right(a, x)
    if i != 0 and a[i-1] == x:
        return (i-1)
    else:
        return -1
 
a  = [1, 2, 4, 4]
x = int(4)
res = BinarySearch(a, x)
if res == -1:
    print(x, "is absent")
else:
    print("Last occurrence of", x, "is present at", res)

Last occurrence of 4 is present at 3

Consulte Búsqueda binaria para escribir su propio código de búsqueda binaria.
Referencia: 
https://docs.python.org/3/library/bisect.html