Comment trouver efficacement une valeur dans un tableau
Utilisez les flèches, cliquez ou glissez pour naviguer
1. Implémenter une recherche linéaire
Parcourir un tableau élément par élément — O(n)
2. Comprendre la recherche binaire
Diviser pour régner — O(log n)
3. Implémenter la recherche binaire
Sur un tableau trié uniquement
4. Pourquoi trier aide à chercher
Le compromis tri/recherche
Recherche linéaire
Parcourir un par un — O(n), simple mais lent
Le jeu du "plus grand, plus petit"
L'analogie parfaite pour la recherche binaire
Recherche binaire
Diviser pour régner — O(log n), nécessite un tableau trié
Live coding
Implémenter les deux algorithmes et comparer
Pourquoi trier d'abord ?
Quand le tri devient rentable
Trouver une valeur spécifique dans un tableau
Exemple : Où se trouve le nombre 42 ?
[3, 7, 12, 42, 89, 156, 201]
Parcourir le tableau élément par élément
Comparer chaque valeur avec celle qu'on cherche
Tableau
On teste chaque case jusqu'à trouver
Simple mais inefficace pour les grands tableaux
// Cherche 'valeur' dans 'tableau'
FONCTION rechercheLineaire(tableau, valeur)
POUR i DE 0 À tableau.longueur - 1
SI tableau[i] = valeur
RETOURNER i // Trouvé! Retourne l'index
FIN SI
FIN POUR
RETOURNER -1 // Non trouvé
FIN FONCTION
On retourne l'index si trouvé, sinon -1
function rechercheLineaire(tableau, valeur) {
for (let i = 0; i < tableau.length; i++) {
if (tableau[i] === valeur) {
return i; // Trouvé!
}
}
return -1; // Non trouvé
}
Exemple d'utilisation :
const nombres = [3, 7, 12, 42, 89];
rechercheLineaire(nombres, 42); // → 3
rechercheLineaire(nombres, 100); // → -1
Dans le pire cas, on parcourt tout le tableau
Si la valeur est à la fin ou absente → n comparaisons
10 éléments
10 ops
1 000 éléments
1 000 ops
1 000 000 éléments
1 000 000 ops
Devinez un nombre entre 1 et 100
Je pense à un nombre... Proposez!
Je répondrai : "Plus grand" ou "Plus petit"
Mauvaise stratégie
1, 2, 3, 4, 5, 6...
Jusqu'à 100 essais!
Bonne stratégie
Commencer par 50 (le milieu)
Diviser par 2 à chaque fois!
Exemple : Le nombre est 73
Au lieu de tester chaque nombre, on divise l'espace de recherche par 2
Recherche linéaire
1, 2, 3, 4, 5... jusqu'à trouver
Jusqu'à 100 essais
Recherche binaire
50 → 75 → 62 → 68 → 71 → 73...
Maximum 7 essais!
log₂(100) ≈ 7 — Seulement 7 étapes max!
Diviser pour régner — O(log n)
À chaque étape, on élimine la moitié des possibilités
Le tableau DOIT être TRIÉ
Si le tableau n'est pas trié, la recherche binaire ne fonctionne PAS
On ne peut pas savoir quelle moitié éliminer!
// Le tableau DOIT être trié!
FONCTION rechercheBinaire(tableau, valeur)
gauche = 0
droite = tableau.longueur - 1
TANT QUE gauche ≤ droite
milieu = (gauche + droite) / 2
SI tableau[milieu] = valeur
RETOURNER milieu // Trouvé!
SINON SI tableau[milieu] < valeur
gauche = milieu + 1 // Chercher à droite
SINON
droite = milieu - 1 // Chercher à gauche
FIN TANT QUE
RETOURNER -1 // Non trouvé
FIN FONCTION
function rechercheBinaire(tableau, valeur) {
let gauche = 0;
let droite = tableau.length - 1;
while (gauche <= droite) {
const milieu = Math.floor((gauche + droite) / 2);
if (tableau[milieu] === valeur) {
return milieu;
} else if (tableau[milieu] < valeur) {
gauche = milieu + 1;
} else {
droite = milieu - 1;
}
}
return -1;
}
Exemple :
const nombres = [3, 7, 12, 42, 89, 156, 201];
rechercheBinaire(nombres, 42); // → 3
Cherchons 42 dans [3, 7, 12, 42, 89, 156, 201]
Étape 1 : milieu = 3 (valeur 42)
Trouvé en 1 seule étape!
Si on cherchait 156 :
42 < 156 → on garde la moitié droite → 156 trouvé à l'étape 2
log₂(1 000 000) ≈ 20
Seulement 20 étapes pour chercher dans 1 million d'éléments!
Recherche linéaire
1 000 000 ops
Recherche binaire
20 ops
| N éléments | O(n) Linéaire | O(log n) Binaire | Ratio |
|---|---|---|---|
| 10 | 10 | ~4 | 2.5x |
| 100 | 100 | ~7 | 14x |
| 1 000 | 1 000 | ~10 | 100x |
| 100 000 | 100 000 | ~17 | 5 882x |
| 1 000 000 | 1 000 000 | ~20 | 50 000x |
Pour 1 million : 50 000 fois plus rapide!
O(log n) reste presque plat même avec des millions d'éléments
Recherche linéaire
O(n)
Recherche binaire
O(log n)
Implémentons les deux algorithmes ensemble
Comparons le nombre d'opérations pour différents tableaux
Les erreurs de décalage sont très fréquentes!
❌ Incorrect
while (gauche < droite) { // < au lieu de <=
milieu = Math.floor((gauche + droite) / 2);
if (tableau[milieu] < valeur) {
gauche = milieu; // Oubli du +1
✅ Correct
while (gauche <= droite) { // <= important!
milieu = Math.floor((gauche + droite) / 2);
if (tableau[milieu] < valeur) {
gauche = milieu + 1; // +1 essentiel
💡 gauche <= droite pour inclure le dernier élément
💡 milieu ± 1 pour éviter de retester le milieu
La recherche binaire ne fonctionne PAS sur un tableau non trié!
❌ Tableau non trié
On ne peut pas diviser intelligemment!
✅ Tableau trié
On peut éliminer la moitié!
Les étudiants oublient souvent cette précondition!
✅ Vérifier les bornes avec des exemples simples
Tester avec tableau = [5] et chercher 5 → doit retourner 0
✅ Toujours vérifier que le tableau est trié
Ajouter un commentaire ou une assertion au début de la fonction
✅ Tester les cas limites
Élément au début, à la fin, absent, tableau vide
1. Recherche linéaire = O(n)
Simple, fonctionne toujours, mais lent pour les grands tableaux
2. Recherche binaire = O(log n)
Ultra rapide, mais nécessite un tableau trié
3. Le jeu "plus grand/plus petit" = recherche binaire
Diviser par 2 à chaque étape → log₂(n) opérations max
Si on effectue plusieurs recherches, le tri devient rentable
1 recherche
Linéaire
Pas besoin de trier
10 recherches
À évaluer
Dépend de la taille
100+ recherches
Binaire + Tri
Très rentable!
Trier = O(n log n), mais ensuite chaque recherche = O(log n)
Pour k recherches : O(n log n) + k × O(log n) vs k × O(n)
1. Implémenter rechercheLineaire()
Tester avec différents tableaux et valeurs
2. Implémenter rechercheBinaire()
Attention aux bornes gauche/droite!
3. Comparer les performances
Créer un tableau de 10 000 éléments et mesurer le temps
4. Défi : Trouver le bug
On vous donne une recherche binaire avec un bug off-by-one
Recherche linéaire vs binaire — Choisir le bon outil
À retenir : log₂(1 000 000) ≈ 20
Seulement 20 étapes pour chercher dans 1 million!