Recherche binaire en C et C++ – Exécuter en ligne

Qu’est-ce que Recherche binaire ?

La recherche binaire élimine la moitié de la zone à chaque comparaison.

Cherchez dans des données triées en temps logarithmique.

Points importants

Testez les entrées vides, uniques, dupliquées et déjà triées.
Séparez correction et optimisation.
Préférez la bibliothèque standard en production.

Visualisation de Recherche binaire

O(log n)

Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.

Exemples de code C et C++

C

Exécuter →

main.c

#include <stdio.h>

int search(const int *values, int size, int target) {
    int low = 0;
    int high = size - 1;
    while (low <= high) {
        int middle = low + (high - low) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) low = middle + 1;
        else high = middle - 1;
    }
    return -1;
}

int main(void) {
    int values[] = {3, 7, 11, 16, 23, 28};
    printf("index=%d\n", search(values, 6, 23));
}

Résultat attendu

index=4

C++

Exécuter →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{3, 7, 11, 16, 23, 28};
    auto match = std::lower_bound(values.begin(), values.end(), 23);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

Résultat attendu

index=4

Comparaison entre C et C++

L’entrée doit être triée. La boucle C et std::lower_bound sont O(log n) sur un accès aléatoire.

C

Boucles, pointeurs, tailles et buffers sont explicites.

C++

Itérateurs et algorithmes séparent opération et stockage.

Exercices pratiques

Exécutez les deux versions puis modifiez-les pour observer leurs garanties.

Tracez chaque comparaison.
Testez doublons et valeurs extrêmes.
Comparez aux algorithmes standards.