close

Algorithme de recherche binaire (Binary Search) en C++- Explication, exemple et code

L'algorithme de recherche binaire est un moyen plus efficace de rechercher un élément spécifique dans une liste triée. Contrairement à la recherche linéaire, qui vérifie les éléments de manière séquentielle, la recherche binaire divise la liste en deux et compare l'élément cible avec l'élément du milieu. Ce processus est répété jusqu'à ce que l'élément cible soit trouvé ou que la plage de recherche devienne vide.

Comment ça fonctionne

  1. Commencez par toute la liste triée.
  2. Trouvez l'élément du milieu de la plage de recherche actuelle.
  3. Comparez l'élément du milieu avec la valeur cible.
  4. Si l'élément du milieu est égal à la valeur cible, la recherche réussit.
  5. Si l'élément du milieu est supérieur à la cible, recherchez dans la moitié gauche de la plage.
  6. Si l'élément du milieu est plus petit que la cible, recherchez dans la moitié droite de la plage.
  7. Répétez les étapes 2 à 6 jusqu'à ce que l'élément cible soit trouvé ou que la plage de recherche soit vide.

Exemple

Considérons une liste triée d'entiers et voulons trouver le nombre 34 en utilisant la recherche binaire.

Liste triée : {12, 23, 34, 45, 56, 67, 89, 90}

  1. Commencez par toute la liste.
  2. Elément central: 56(position 4). Comparez avec 34.
  3. 56 est supérieur à 34. Rechercher dans la moitié gauche.
  4. Nouvel élément central: 23(position 1). Comparez avec 34.
  5. 23 est plus petit que 34. Cherchez dans la moitié droite.
  6. Nouvel élément central: 45(position 3). Comparez avec 34.
  7. 45 est supérieur à 34. Rechercher dans la moitié gauche.
  8. Nouvel élément central: 34(position 2). Cible trouvée.

Exemple de code en C++ 

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}

Dans l'exemple donné, la binarySearch fonction est utilisée pour trouver le nombre 34 dans une liste triée d'entiers. Le résultat sera la position 34 dans la liste(les positions commencent à 0) ou -1 si le numéro n'est pas trouvé.