Ricerca binaria Python
Harshit Jindal
3 gennaio 2023
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
locome0ehicomen - 1. -
Mentre
lo<hi, impostamid=lo + (hi - lo)/2.- Se
A[mid]==X, abbiamo trovato che l’elemento restituisce l’indicemid. - Se
A[mid]<X, allora scarta la metà sinistra degli elementi e impostalocomemid+1. - Altrimenti se
A[mid]>X, allora scarta la metà destra degli elementi e impostahicomemid-1.
- Se
-
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
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.
LinkedIn