|
Author: Eduardo Enriquez
Python: binary search algorithm (búsqueda binaria)
La búsqueda binaria es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado. Lo que hace el algoritmo es empezar a comparar valores desde la mitad de mi lista o array. En el caso de que sea mayor el numero buscado, el algoritmo seguira buscando a partir de la mitad restante de la derecha y también a partir de la mitad.
La búsqueda binaria tiene en el peor de los casos un tiempo logarítmico, realizando O(log n) comparaciones, donde n es el número de elementos del array and log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array.
def binary_search(number, aList):
left = 0
right = len(aList)
found = False
while left < right:
mid = (left + right) / 2
if aList[mid] < number:
left = mid + 1
else:
right = mid
if number == aList[left]:
found = True
position = left
return found, position
return found