HOWTO · Python

Ricerca binaria Python

Questo tutorial mostra come utilizzare l'algoritmo di ricerca binaria in Python.

Di Harshit JindalPubblicato 2021-03-30Aggiornato 2023-01-03
In questa pagina
Nota
Se si desidera comprendere in dettaglio la ricerca binaria, fare riferimento all’articolo algoritmo di ricerca binaria.

Algoritmo di ricerca binaria

Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento X.

  • Imposta lo come 0 e hi come n - 1.
  • Mentre lo <hi, imposta mid = lo + (hi - lo)/2.
    • Se A[mid] == X, abbiamo trovato che l’elemento restituisce l’indice mid.
    • Se A[mid] <X, allora scarta la metà sinistra degli elementi e imposta lo come mid+1.
    • Altrimenti se A[mid]> X, allora scarta la metà destra degli elementi e imposta hi come mid-1.
  • L’elemento non è stato trovato, quindi restituisci -1.

Programma Python per la ricerca 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))

Produzione:

Element is present at index 2

Informazioni sull’autore

Harshit Jindal

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.

Visualizza il profilo dell’autore
LinkedIn