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á ordenado al ignorar la mitad de los elementos después de una sola comparación. 

1. Compara x con el elemento del medio.
2. Si x coincide con el elemento medio, devolvemos el índice medio.
3. De lo contrario, si x es mayor que el elemento medio, entonces x solo puede estar en el medio subarreglo derecho (mayor) después del elemento medio. Luego aplicamos el algoritmo nuevamente para la mitad derecha.
4. De lo contrario, si x es menor, el objetivo x debe estar en la mitad izquierda (inferior). Así que aplicamos el algoritmo para la mitad izquierda.

recursivo:

# 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 de tiempo : O (log n)

Espacio auxiliar : O (inicio de sesión) [NOTA: la recursividad crea la pila de llamadas]

Iterativo:
 

# 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] < x:
            low = mid + 1
 
        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1
 
        # means x is present at mid
        else:
            return mid
 
    # If we reach here, then the element was not present
    return -1
 
 
# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
# Function call
result = binary_search(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 de tiempo : O (log n)

Espacio auxiliar : O(1) ¡
Consulte el artículo Búsqueda binaria para obtener más detalles!