Ricerca di un elemento in un array in C

La ricerca di un elemento in un array è una delle operazioni fondamentali in informatica. È una competenza di base per ogni programmatore e un concetto chiave nei corsi di algoritmi e strutture dati. Esistono diversi algoritmi per la ricerca, ognuno con i suoi vantaggi e svantaggi. In questa pagina esploreremo i metodi più comuni per cercare un elemento in un array in C: la ricerca lineare e la ricerca binaria.

Ricerca lineare

La ricerca lineare è il metodo più semplice per trovare un elemento in un array. Questo algoritmo scorre l'array dall'inizio alla fine, confrontando ogni elemento con il valore cercato. Se trova una corrispondenza, restituisce l'indice dell'elemento; altrimenti, restituisce un valore indicante che l'elemento non è stato trovato.

Implementazione della ricerca lineare in C

Ecco un esempio di come implementare la ricerca lineare in C:

#include <stdio.h>

// Funzione per la ricerca lineare
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Elemento trovato, restituisce l'indice
        }
    }
    return -1; // Elemento non trovato
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = linearSearch(arr, n, target);
    if (result != -1) {
        printf("Elemento trovato all'indice %d\n", result);
    } else {
        printf("Elemento non trovato\n");
    }

    return 0;
}

La funzione linearSearch scorre l'array arr di dimensione size alla ricerca del target. Se trova il target, restituisce l'indice; altrimenti, restituisce -1.

La funzione main testa la funzione di ricerca lineare con un esempio di array e un valore target.

Complessità temporale della ricerca lineare

La ricerca lineare ha una complessità temporale di O(n), dove n è il numero di elementi nell'array. Questo significa che nel peggiore dei casi (quando l'elemento cercato è l'ultimo o non è presente), l'algoritmo deve controllare tutti gli elementi dell'array.

Ricerca binaria

La ricerca binaria è un algoritmo molto più efficiente rispetto alla ricerca lineare, ma richiede che l'array sia ordinato. La ricerca binaria divide ripetutamente l'array a metà, confrontando il valore cercato con l'elemento centrale dell'array. Se il valore cercato è uguale all'elemento centrale, l'algoritmo restituisce l'indice. Se il valore cercato è minore dell'elemento centrale, l'algoritmo continua la ricerca nella metà sinistra dell'array; altrimenti, continua nella metà destra.

Implementazione della ricerca binaria in C

Ecco un esempio di come implementare la ricerca binaria in C:

#include <stdio.h>

// Funzione per la ricerca binaria
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // Elemento trovato, restituisce l'indice
        }
        if (arr[mid] < target) {
            left = mid + 1; // Cerca nella metà destra
        } else {
            right = mid - 1; // Cerca nella metà sinistra
        }
    }
    return -1; // Elemento non trovato
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, n, target);
    if (result != -1) {
        printf("Elemento trovato all'indice %d\n", result);
    } else {
        printf("Elemento non trovato\n");
    }

    return 0;
}

La funzione binarySearch divide l'array a metà e confronta il valore centrale con il target. A seconda del risultato, restringe la ricerca a una delle due metà.

La funzione main testa la funzione di ricerca binaria con un esempio di array ordinato e un valore target.

Complessità temporale

La ricerca binaria ha una complessità temporale di O(log n), dove n è il numero di elementi nell'array. Questo significa che l'algoritmo è molto più efficiente della ricerca lineare, specialmente per array di grandi dimensioni.

La ricerca di un elemento in un array è un'operazione cruciale in molte applicazioni. La scelta dell'algoritmo di ricerca dipende dalla struttura dell'array e dai requisiti di efficienza dell'applicazione. La ricerca lineare è semplice e versatile, mentre la ricerca binaria è molto più efficiente ma richiede un array ordinato.