Búsqueda binaria en Python

Harshit Jindal 30 enero 2023 Python Python Algorithm
  1. Algoritmo de búsqueda binaria
  2. Programa Python para búsqueda binaria
Búsqueda binaria en Python
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 lo como 0 y hi como n - 1.
  • Mientras que lo < hi, establezca mid = lo + (hi - lo)/2.
    • Si A[mid] == X, hemos encontrado que el elemento devuelve el índice mid.
    • Si A[mid] < X, descarte la mitad izquierda de los elementos y establezca lo como mid+1.
    • De lo contrario, si A[mid] > X, descarte la mitad derecha de los elementos y establezca hi como mid-1.
  • 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
¿Disfrutas de nuestros tutoriales? Suscríbete a DelftStack en YouTube para apoyarnos en la creación de más guías en vídeo de alta calidad. Suscríbete
Autor: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Artículo relacionado - Python Algorithm