El paso a paso o código que verás en este post es la resolución más sencilla y efectiva que hallamos a esta duda o dilema.
Solución:
bisect_left encuentra la primera posición p en el que se podría insertar un elemento en un rango ordenado dado mientras se mantiene el orden ordenado. Esa será la posición de x Si x existe en el rango. Si p es la posición más allá del final, x no fue encontrado De lo contrario, podemos probar para ver si x hay para ver si x fue encontrado.
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 miras el código de bisect_left/right y lo adaptas a tu 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
Esto está un poco fuera de tema (ya que la respuesta de Moe parece completa a la pregunta del OP), pero podría valer la pena analizar la complejidad de todo su procedimiento de principio a fin. Si está almacenando cosas en listas ordenadas (que es donde ayudaría una búsqueda binaria), y luego solo verifica la existencia, está incurriendo (en el peor de los casos, a menos que se especifique):
Listas ordenadas
- O(n log n) para crear inicialmente la lista (si son datos sin clasificar. O(n), si están ordenados)
- Búsquedas O(log n) (esta es la parte de búsqueda binaria)
- O(n) insertar/borrar (puede ser O(1) u O(log n) caso promedio, dependiendo de su patrón)
Mientras que con un set()estás incurriendo
- O(n) para crear
- Búsqueda O(1)
- O(1) insertar/eliminar
Lo que realmente obtiene una lista ordenada es “siguiente”, “anterior” y “rangos” (incluida la inserción o eliminación de rangos), que son O(1) u O(|rango|), dado un índice inicial. Si no usa ese tipo de operaciones con frecuencia, entonces almacenar como conjuntos y ordenar para mostrar podría ser una mejor opción en general. set() incurre en muy poca sobrecarga adicional en python.
Sección de Reseñas y Valoraciones
Si posees alguna cuestión o capacidad de aumentar nuestro escrito eres capaz de dejar una anotación y con placer lo interpretaremos.