cota superior de un conjunto
def lower_bound(a, c):
#Inferior (Izq) el mas grande de los pequeños
ans = -1
if a[0] >= c: ans = -1
else:
low, hi = 0, len(a)
while low+1 != hi:
mid = low + ((hi-low)//2)
if a[mid] < c: low = mid
else:
hi = mid
ans = low
return ans
def upper_bound(a, c):
#superior (Der) el mas pequeño de los grandes
ans = -1
if a[len(a)-1] <= c: ans = -1
else:
low, hi = 0, len(a)
while low+1 != hi:
mid = low + ((hi-low)//2)
if a[mid-1] > c: hi = mid
else:
low = mid
ans = low
return ans
# El algoritmo retorna el indice que cumple con la definición.
# si retorna -1.. el valor no se puede encontrar en a ; a es una lista ordenada ascendentemente de números natural.
# Se llama así: print( down_bound(L, c), upper_bound(L, c) )