Edizione didattica italiana

Ricerca binaria in un array C

Cerca una chiave in un array ordinato dimezzando l’intervallo a ogni passo.

Leggi N, la chiave K e un array in ordine non decrescente. Restituisci l’indice a partire da zero di un’occorrenza di K, oppure -1 se assente.

Confronta la chiave con l’elemento centrale ed elimina la metà che non può contenerla. Con duplicati va bene qualsiasi occorrenza: non è richiesta necessariamente la prima.

Input

N e K, poi N interi ordinati in modo non decrescente.

Output

Found at index: <indice> se presente, altrimenti Not found: -1.

Vincoli

1 ≤ N ≤ 100000; valori da -10⁹ a 10⁹.
Ricerca in O(log N) tempo e O(1) memoria aggiuntiva.

Suggerimenti

Inizia con low = 0 e high = N - 1 e prosegui finché low <= high.
Calcola mid = low + (high - low) / 2 evitando la somma diretta dei limiti.
Dopo un confronto senza uguaglianza usa high = mid - 1 oppure low = mid + 1.

Codice sorgente

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Apri nel compilatore

Spiegazione della soluzione

Mantieni l’invariante: se la chiave è nella zona restante, il suo indice è tra low e high inclusi. L’uguaglianza termina subito la ricerca.

Quando low supera high non rimangono candidati: restituisci -1. La ricerca è logaritmica, ma leggere N valori richiede comunque O(N) tempo.

Codice della soluzione

#include <stdio.h>

int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        // Overflow-safe midpoint calculation
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

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.