>>35884
continuo
consideremos primero una implementacion en python del algoritmo de busqueda binaria
def binary_search(haystack, needle, lower=None, upper=None):
''' dada una secuencia l ordenada, si el elemento x esta en la secuencia
hallamos i tal que l[i] = x
'''
if lower == None: # primera llamada a la funcion
lower = 0
upper = len(haystack)
midpoint = (lower+upper)//2
if upper > lower+1: # verificamos que hayan elementos entre
# haystack[lower] y haystack[upper]
# de no haberlos, no se logro encontrar el elemento
if needle == haystack[midpoint]:
return midpoint
elif needle > haystack[midpoint]:
return binary_search(haystack, needle, midpoint, upper)
elif needle < haystack[midpoint]:
return binary_search(haystack, needle, lower, midpoint)
else:
raise Exception('no se hallo el elemento')
podemos hacer algunos cambios para llegar a la version continua del algoritmo. para empezar, haystack no seria un arreglo sino una funcion, asi que en vez de hacer haystack[x] hacemos haystack(x). tambien el valor medio entre a y b ya no es un numero entero, asi que hacemos midpoint = (a+b)/2 en vez de midpoint = (a+b)//2
por otro lado, tenemos que definir un intervalo en el que creamos que se puede conseguir la solucion y en el que la funcion sea creciente, asi que nuestra nueva funcion recibira dos parametros mas para los limites del intervalo.
dadas las limitaciones de los numeros de punto flotante, no podemos comparar la equivalencia de needle y haystack[midpoint] para ver si conseguimos la solucion, sino que tenemos que establecer que tan precisa quieremos nuestra solucion, asi que cambiamos el needle == haystack[midpoint] por abs(needle, haystack[midpoint]) < EPSILON, para alguna constante epsilon.
finalmente, no nos sirve revisar si upper es el sucesor de lower para ver si no hay mas elementos que inspeccionar. asi que en vez de revisar si upper>lower+1, revisamos si abs(upper-lower)>EPSILON, queriendo ver si el intervalo es lo suficientemente grande para pensar que la solucion podria estar en el. asi tenemos,
def bisect(haystack, needle, lower, upper):
''' dada una funcion f: R->R, hallamos la solucion de f(x)=y en un intervalo
(lower, upper)
'''
midpoint = (lower+upper)/2
if abs(upper-lower) > EPSILON:
if abs(needle-haystack(midpoint)) < EPSILON:
return midpoint
elif needle > haystack(midpoint):
return bisect(haystack, needle, midpoint, upper)
elif needle < haystack(midpoint):
return bisect(haystack, needle, lower, midpoint)
else:
raise Exception('no se hallo el elemento')
mas alla, podemos garantizar que el algoritmo de biseccion va a funcionar si haystack(lower) <= needle <= haystack(upper), gracias al teorema del valor intermedio: https://es.wikipedia.org/wiki/Teorema_del_valor_intermedio