HOWTO · Python
Búsqueda binaria en Python
Este tutorial demuestra cómo utilizar el algoritmo de búsqueda binaria en Python.
En esta página
Nota
Si desea comprender la búsqueda binaria en detalle, consulte el artículo algoritmo de búsqueda binaria.
Algoritmo de búsqueda binaria
Supongamos que tenemos un array sin clasificar A[] que contiene n elementos, y queremos encontrar un elemento X.
-
Establece
locomo0yhicomon - 1. -
Mientras que
lo<hi, establezcamid=lo + (hi - lo)/2.- Si
A[mid]==X, hemos encontrado que el elemento devuelve el índicemid. - Si
A[mid]<X, descarte la mitad izquierda de los elementos y establezcalocomomid+1. - De lo contrario, si
A[mid]>X, descarte la mitad derecha de los elementos y establezcahicomomid-1.
- Si
-
El elemento no se encuentra, así que devuelve
-1.
Programa Python para búsqueda binaria
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 1, 5]
x = 4
n = len(arr)
result = binary_search(arr, x, n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
Producción :
Element is present at index 2
