Programa Python para búsqueda binaria (recursiva e iterativa)
En pocas palabras, este algoritmo de búsqueda aprovecha una colección de elementos que ya están ordenados ignorando la mitad de los elementos después de una sola comparación.
- Compara x con el elemento del medio.
- Si x coincide con el elemento del medio, devolvemos el índice medio.
- De lo contrario, si x es mayor que el elemento medio, entonces x solo puede estar en la mitad del subconjunto derecho (mayor) después del elemento medio. Luego aplicamos nuevamente el algoritmo para la mitad derecha.
- De lo contrario, si x es menor, el objetivo x debe estar en la mitad izquierda (inferior). Entonces aplicamos el algoritmo para la mitad izquierda.
Programa Python para búsqueda binaria mediante recursivo
Python3
# Python 3 program for recursive binary search.> # Modifications needed for the older Python 2 are found in comments.> # Returns index of x in arr if present, else -1> def> binary_search(arr, low, high, x):> > # Check base case> > if> high>> => low:> > mid> => (high> +> low)> /> /> 2> > # If element is present at the middle itself> > if> arr[mid]> => => x:> > return> mid> > # If element is smaller than mid, then it can only> > # be present in left subarray> > elif> arr[mid]>x:> > return> binary_search(arr, low, mid> -> 1> , x)> > # Else the element can only be present in right subarray> > else> :> > return> binary_search(arr, mid> +> 1> , high, x)> > else> :> > # Element is not present in the array> > return> -> 1> # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> # Function call> result> => binary_search(arr,> 0> ,> len> (arr)> -> 1> , x)> if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Producción
Element is present at index 3
Complejidad del tiempo : O(log n)
Espacio Auxiliar : O(logn) [NOTA: La recursividad crea una pila de llamadas]
Programa Python para búsqueda binaria mediante iterativo
Python3
# Iterative Binary Search Function> # It returns index of x in given array arr if present,> # else returns -1> def> binary_search(arr, x):> > low> => 0> > high> => len> (arr)> -> 1> > mid> => 0> > while> low <> => high:> > mid> => (high> +> low)> /> /> 2> > # If x is greater, ignore left half> > if> arr[mid] low = mid + 1 # If x is smaller, ignore right half elif arr[mid]>x: high = mid - 1 # significa que x está presente en mid else: return mid # Si llegamos aquí, entonces el elemento no estaba presente return -1 # Probar matriz arr = [ 2, 3, 4, 10, 40 ] x = 10 # Resultado de llamada a función = binario_search(arr, x) if resultado!= -1: print('Elemento está presente en el índice', str(resultado)) else: print('Elemento no está presente en la matriz ')> |
Producción
Element is present at index 3
Complejidad del tiempo : O(log n)
Espacio Auxiliar :O(1)
Programa Python para búsqueda binaria usando el módulo bisect incorporado
Enfoque paso a paso:
- El código importa el módulo bisect que brinda soporte para la búsqueda binaria.
- Se define la función binario_search_bisect() que toma una matriz arr y el elemento para buscar x como entradas.
- La función llama a la función bisect_left() del módulo bisect que encuentra la posición del elemento en la matriz ordenada arr donde se debe insertar x para mantener el orden. Si el elemento ya está presente en la matriz, esta función devolverá su posición.
- Luego, la función verifica si el índice devuelto i está dentro del rango de la matriz y si el elemento en ese índice es igual a x.
- Si la condición es verdadera, entonces la función devuelve el índice i como la posición del elemento en la matriz.
- Si la condición es falsa, la función devuelve -1, lo que indica que el elemento no está presente en la matriz.
- Luego, el código define una matriz arr y un elemento x para buscar.
- La función binario_search_bisect() se llama con arr y x como entradas y el resultado devuelto se almacena en la variable de resultado.
- Luego, el código verifica si el resultado no es igual a -1, lo que indica que el elemento está presente en la matriz. Si es verdadero, imprime la posición del elemento en la matriz.
- Si el resultado es igual a -1, entonces el código imprime un mensaje de que el elemento no está presente en la matriz.
Python3
import> bisect> > def> binary_search_bisect(arr, x):> > i> => bisect.bisect_left(arr, x)> > if> i !> => len> (arr)> and> arr[i]> => => x:> > return> i> > else> :> > return> -> 1> > > # Test array> arr> => [> 2> ,> 3> ,> 4> ,> 10> ,> 40> ]> x> => 10> > # Function call> result> => binary_search_bisect(arr, x)> > if> result !> => -> 1> :> > print> (> 'Element is present at index'> ,> str> (result))> else> :> > print> (> 'Element is not present in array'> )> |
Producción
Element is present at index 3
Complejidad del tiempo : O(log n)
Espacio Auxiliar :O(1)
