Édition pédagogique en français

Recherche dichotomique dans un tableau en C

Recherchez une valeur dans un tableau trié en divisant l’intervalle de recherche par deux.

Lisez N, la valeur cible K et un tableau trié par ordre croissant au sens large. Renvoyez l’indice commençant à zéro d’une occurrence de K, ou -1 si cette valeur est absente.

Comparez la cible à l’élément central et éliminez la moitié qui ne peut pas la contenir. En présence de doublons, n’importe quelle occurrence convient ; l’exercice ne demande pas obligatoirement la première.

Entrée

N et K, puis N entiers triés par ordre non décroissant.

Sortie

Found at index: <indice> si la cible existe, sinon Not found: -1.

Contraintes

1 ≤ N ≤ 100000 ; valeurs entre -10⁹ et 10⁹.
Recherche en O(log N) temps avec O(1) mémoire supplémentaire.

Indices

Initialisez low = 0 et high = N - 1 ; poursuivez tant que low <= high.
Calculez mid = low + (high - low) / 2 pour éviter la somme directe des bornes.
Après une comparaison sans égalité, utilisez high = mid - 1 ou low = mid + 1.

Code source

#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;
}

Ouvrir dans le compilateur

Explication de la solution

Conservez l’invariant suivant : si la cible est présente dans la zone restante, son indice se trouve entre low et high inclus. L’égalité termine la recherche immédiatement.

Quand low dépasse high, aucune position candidate ne reste : renvoyez -1. La recherche est logarithmique, mais lire les N valeurs demande toujours O(N) temps.

Code de la solution

#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;
}

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.