Se utiliza cuando el vector en el que queremos determinar la existencia de
un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda
considerablemente, ya que disminuye exponencialmente el número de iteraciones
necesarias.
Está altamente recomendado para buscar en arrays de gran tamaño. Por
ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26
comparaciones (en el peor de los casos).
Para implementar este algoritmo se compara el elemento a buscar con un
elemento cualquiera del array (normalmente el elemento central): si el valor de
éste es mayor que el del elemento buscado se repite el procedimiento en la
parte del array que va desde el inicio de éste hasta el elemento tomado, en
caso contrario se toma la parte del array que va desde el elemento tomado hasta
el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que
se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de
este último entonces se deduce que el elemento buscado no se encuentra en todo
el array.
A continuación se muestra el código para este tipo de bùsqueda en Python:
#BUSQUEDA BINARIA
def BubbleSort(A,n):
i=0
while(i<=(n-2)):
j=0
while(j<=(n-2-i)):
if (A[j+1]<A[j]):
a=A[j]
A[j]=A[j+1]
A[j+1]=a
j=j+1
i=i+1
return A
def BusquedaBinaria(C,B,j):
if(B==int(C[j])):
return 1,j
else:
if(len(C)==1 or j<1):
return 0,j
if(B<C[j]):
return BusquedaBinaria(C[:j],B,j/2)
else:
return BusquedaBinaria(C[j+1:],B,j/2)
a=[]
prueba = [1,50,34,2,7,788]
valorABuscar=7
C=BubbleSort(prueba,len(prueba))
i=0
while (i<len(prueba)):
a.append(int(C[i]))
i=i+1
if((len(a)%2)==0):
j=((len(a)/2)-1)
else:
j=(len(a)/2)
x,y=BusquedaBinaria(a,valorABuscar,j)
if(x==1):
print ("Numero encontrado")
else:
print ("Numero no encontrado")