Búsqueda binaria (bisección) en Python
¿Existe una función de biblioteca que realice una búsqueda binaria en una lista/tupla y devuelva la posición del elemento si se encuentra y 'Falso' (-1, Ninguno, etc.) en caso contrario?
Encontré las funciones bisect_left/right en el módulo bisect , pero aún devuelven una posición incluso si el elemento no está en la lista. Eso está perfectamente bien para el uso previsto, pero solo quiero saber si un elemento está en la lista o no (no quiero insertar nada).
Pensé en usar bisect_lefty luego verificar si el elemento en esa posición es igual a lo que estoy buscando, pero eso parece engorroso (y también necesito verificar con límites si el número puede ser mayor que el número más grande de mi lista). Si hay un método mejor, me gustaría saberlo.
Editar Para aclarar para qué necesito esto: soy consciente de que un diccionario sería muy adecuado para esto, pero estoy tratando de mantener el consumo de memoria lo más bajo posible. Mi uso previsto sería una especie de tabla de consulta de doble vía. Tengo en la tabla una lista de valores y necesito poder acceder a los valores según su índice. Y también quiero poder encontrar el índice de un valor particular o Ninguno si el valor no está en la lista.
Usar un diccionario para esto sería la forma más rápida, pero duplicaría (aproximadamente) los requisitos de memoria.
Estaba haciendo esta pregunta pensando que tal vez había pasado por alto algo en las bibliotecas de Python. Parece que tendré que escribir mi propio código, como sugirió Moe.
bisect_leftencuentra la primera posición pen la que se podría insertar un elemento en un rango ordenado determinado manteniendo el orden de clasificación. Esa será la posición de xsi xexiste en el rango. Si pes la posición más allá del final, xno se encontró. De lo contrario, podemos probar para ver si xestá ahí y si xse encontró.
from bisect import bisect_left
def binary_search(a, x, lo=0, hi=None):
if hi is None: hi = len(a)
pos = bisect_left(a, x, lo, hi) # find insertion position
return pos if pos != hi and a[pos] == x else -1 # don't walk off the end
¿Por qué no mirar el código de bisect_left/right y adaptarlo a su propósito?
como esto:
def binary_search(a, x, lo=0, hi=None):
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
midval = a[mid]
if midval < x:
lo = mid+1
elif midval > x:
hi = mid
else:
return mid
return -1
