¿Qué es la búsqueda binaria??

Una búsqueda binaria es un algoritmo de búsqueda utilizado para buscar elementos objetivo en un contenedor donde los elementos deben organizarse en orden ascendente. En general, la búsqueda binaria se usa para buscar el número de índice del elemento de destino en una matriz ordenada.

La búsqueda binaria utiliza el enfoque de división y conquista, en el que divide la matriz en partes iguales hasta que encuentre el elemento objetivo.

Se implementa un algoritmo de búsqueda binario iterativo y una declaración recursiva. La búsqueda binaria es más eficiente y más rápida en comparación con la búsqueda lineal.

Algoritmo de búsqueda binaria

1. Ordena y organiza los elementos en la matriz arrugado en orden ascendente.
2. Los algoritmos comparan el elemento medio norte con el elemento objetivo objetivo.
3. El algoritmo devuelve el índice de posición del elemento medio si se encuentra que el elemento de destino es igual al elemento medio,
4. El algoritmo busca la mitad inferior de la matriz si el elemento de destino es menor que el elemento medio.
5. El algoritmo busca la mitad superior de la matriz si el elemento de destino es mayor que el elemento medio.
6. El algoritmo sigue repitiendo los pasos 4 y quinto hasta que la longitud de la matriz se convierte en uno o menos de 1.

Al final, se devuelve el valor de índice del elemento o el elemento no existe en la matriz.

Seudocódigo de búsqueda binaria

Iterativo

función binary_search (arr, n, target) es
Izquierda: = 0
Derecha: = N - 1
Mientras que la izquierda ≤ derecha lo hace
Middle: = piso ((izquierda + derecha) / 2)
Si ARR [Middle] objetivo entonces
Derecha: = Medio - 1
demás:
regresar en el medio
volver sin éxito

Recursivo

función binary_search (arr, izquierda, derecha, destino) es
Si a la derecha> = izquierda
medio = (izquierda+derecha) // 2
Si arr [medio] == objetivo
regresar en el medio
más si arr [medio]> tarrget
return binary_search (arr, bajo, mid-1, objetivo)
demás
return binary_search (arr, mid+1, derecha, objetivo)
demás
volver sin éxito

Implementar la búsqueda binaria en Python

Iterativo
En el enfoque iterativo, utilizamos los bucles para implementar la búsqueda binaria.

def binary_search (arr, n, objetivo):
izquierda = 0
Derecha = N-1
medio = 0
Mientras está a la izquierda<=right:
medio = (derecho+izquierda) // 2
#Se el elemento medio es igual al elemento objetivo
Si arr [medio] == Target:
regresar en el medio
# Si el elemento objetivo es mayor que el elemento medio
Elif arr [medio]< target:
Izquierda = Medio+1
# Si el elemento objetivo es menos que el elemento medio
demás:
Right = Middle-1
# Si el elemento objetivo no está presente en la matriz
retorno -1
Si __name__ == '__main__':
# matriz ordenada
Sorted_arr = [0,4,7,10,14,23,45,47,53]
# Longitud de la matriz
n = len (sorted_arr)
#Element para buscar
objetivo = 47
posición = binary_search (sorted_arr, n, objetivo)
Si la posición != -1:
print (f "elemento target presente en el índice posición")
demás:
print (f "elemento target no presenta en la matriz")

Producción

Elemento 47 presente en el índice 7

Recursivo
En recursivo en lugar de usar bucle, seguimos llamando a la función una y otra vez hasta que la condición base se satisfaga

def binary_search (arr, izquierda, derecha, objetivo):
#condición de base
Si RightTarget:
return binary_search (arr, izquierda, medio-1, objetivo)
#IF El elemento objetivo es más pequeño que el elemento medio
demás:
return binary_search (arr, medio+1, derecha, objetivo)
Si __name__ == '__main__':
# matriz ordenada
Sorted_arr = [0,4,7,10,14,23,45,47,53]
izquierda = 0
right = len (sorted_arr) -1
#Element para buscar
objetivo = 47
posición = binary_search (sorted_arr, izquierda, derecha, objetivo)
Si la posición != -1:
print (f "elemento target presente en el índice posición")
demás:
print (f "elemento target no presenta en la matriz")

Producción

El elemento 90 no está presente en la matriz

Complejidad

La búsqueda binaria tiene una complejidad de tiempo de o (log n), donde norte es el número de elementos presentes en la matriz.

La búsqueda binaria tiene una complejidad espacial de O (1) porque, en el algoritmo, estamos realizando la búsqueda en el lugar.

Conclusión

La búsqueda binaria es uno de los mejores y eficientes algoritmos de búsqueda. La complejidad del tiempo y el espacio de la búsqueda binaria también es muy baja; El único requisito previo de búsqueda binaria es que la matriz de entrada debe clasificarse en orden ascendente.