Búsqueda binaria en Python
Ejemplos de Python3La búsqueda binaria es un algoritmo de búsqueda que encuentra un elemento específico en un arreglo ordenado. El proceso de búsqueda comienza con el elemento central del arreglo; si el elemento central es exactamente el elemento buscado, el proceso de búsqueda finaliza; si un elemento específico es mayor o menor que el elemento central, se busca en la mitad del arreglo que es mayor o menor que el elemento central, y se comienza comparando desde el elemento central igual que al inicio. Si en algún paso el arreglo está vacío, significa que no se encontró. Este algoritmo de búsqueda reduce el rango de búsqueda a la mitad en cada comparación.
Ejemplo: recursividad
# Devuelve el índice de x en arr, si no existe devuelve -1
def binarySearch (arr, l, r, x):
# Comprobación básica
if r >= l:
mid = int(l + (r - l)/2)
# El elemento está exactamente en la posición intermedia
if arr[mid] == x:
return mid
# Si el elemento es menor que el elemento en la posición central, solo se necesita comparar los elementos de la izquierda
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Si el elemento es mayor que el elemento en la posición central, solo se necesita comparar los elementos de la derecha
else:
return binarySearch(arr, mid+1, r, x)
else:
# No existe
return -1
# Arreglo de prueba
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Llamada a la función
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("El índice del elemento en el arreglo es %d" % result )
else:
print ("El elemento no está en el arreglo")
El resultado de ejecutar el código anterior es:
元素在数组中的索引为 3Otras extensiones