Ricerca binaria Python
Harshit Jindal
3 gennaio 2023
Python
Python Algorithm
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
Ti piacciono i nostri tutorial? Iscriviti a DelftStack su YouTube per aiutarci a creare altre guide video di alta qualità. Iscriviti
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