CodeUtility
Faciliter la vie des développeurs !
Algorithmes C/C++

La recherche dichotomique en C et C++

Dans cette leçon, vous allez chercher dans un tableau trié en O(log n), avec une boucle écrite à la main en C et avec std::lower_bound en C++.

Introduction

La recherche dichotomique compare la valeur cherchée à l'élément situé au milieu de la zone de recherche, puis élimine la moitié qui ne peut pas la contenir. En répétant l'opération, la zone se réduit très vite, mais les données d'entrée doivent obligatoirement être triées.

Points importants

  • Testez avec une entrée vide, un seul élément, des doublons et des données déjà triées.
  • Rendez d'abord le code correct, optimisez ensuite.
  • Dans du vrai code, préférez les fonctions toutes prêtes de la bibliothèque standard.

Visualisation de La recherche dichotomique en C et C++

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 de l’exécution
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 de l’exécution
index=4

Comparaison entre C et C++

Dans la version C, la position du milieu se calcule avec low + (high - low) / 2 plutôt qu'avec (low + high) / 2, pour éviter un débordement quand les indices sont très grands. À chaque comparaison, low ou high se déplace vers la moitié restante. La version C++ utilise std::lower_bound pour trouver la première position qui n'est pas inférieure à la valeur cherchée. Les deux ont une complexité de O(log n).

C

Les boucles, les pointeurs, les longueurs et les tampons temporaires sont écrits explicitement.

C++

Les itérateurs et les algorithmes standard séparent le traitement de la façon dont les données sont stockées.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

  • Déroulez chaque comparaison sur papier.
  • Testez avec des doublons et des valeurs très grandes et très petites.
  • Mesurez le temps d'exécution de votre code et comparez-le à la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis