Édition pédagogique en français

Recherche binaire en C

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

La recherche binaire exige un tableau trié. Comparez la cible à l’élément central : si elle est plus petite, éliminez la moitié droite ; si elle est plus grande, éliminez la gauche. Une égalité donne l’indice recherché.

Calculez le milieu avec low + (high - low) / 2 pour éviter d’additionner deux grands indices. Excluez le milieu déjà testé lors de la mise à jour des bornes. Si low dépasse high, la valeur est absente.

La version itérative coûte O(log N) en temps et O(1) en espace auxiliaire. Testez les extrémités, une valeur absente et un tableau d’un élément. Avec des doublons, l’indice renvoyé n’est pas forcément la première occurrence.

Code source

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

Ouvrir dans le compilateur

Résultat attendu

Element 23 found at index 5

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.