Edizione didattica italiana
Esempio di ricerca binaria in C
Trova un elemento in un array ordinato dimezzando l’intervallo di ricerca.
La ricerca binaria richiede un array ordinato. Confronta la chiave con l’elemento centrale: se è minore scarta la metà destra, se è maggiore scarta la sinistra. L’uguaglianza fornisce l’indice cercato.
Calcola il centro con low + (high - low) / 2 per evitare la somma di indici grandi. Escludi il centro già verificato quando aggiorni i limiti. Se low supera high, la chiave è assente.
La versione iterativa richiede O(log N) tempo e O(1) spazio ausiliario. Prova estremi, valori assenti e un solo elemento. Con duplicati, l’indice restituito non è necessariamente la prima occorrenza.
Codice sorgente
#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
// Prevent (low + high) integer overflow
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1; // Target not found
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 23;
int result = binarySearch(arr, n, target);
if (result != -1)
printf("Element %d found at index %d\n", target, result);
else
printf("Element %d not present\n", target);
return 0;
}Risultato atteso
Element 23 found at index 5
Domande frequenti
Perché il codice e alcuni risultati restano in inglese?
Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.