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

La recherche linéaire en C et C++

Dans cette leçon, vous allez trouver la position d'une valeur dans un tableau non trié avec l'algorithme de recherche linéaire.

Introduction

La recherche linéaire examine les éléments un par un depuis le début du tableau, jusqu'à trouver la valeur cherchée ou atteindre la fin. C'est l'algorithme de recherche le plus simple, et il fonctionne même quand les données ne sont pas 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 linéaire en C et C++

O(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 find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}
Résultat de l’exécution
index=3
C++
Exécuter →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}
Résultat de l’exécution
index=3

Comparaison entre C et C++

Les deux versions ont une complexité de O(n) dans le pire des cas. La fonction find en C renvoie un indice de type int signé, elle peut donc utiliser -1 pour signaler que la valeur est introuvable. La version C++ utilise std::find, qui renvoie un itérateur : s'il est égal à values.end(), la valeur n'est pas dans le tableau.

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