Recherche dichotomique en C++ utilisant un tableau dynamique

Introduction

La recherche dichotomique est une méthode de recherche qui trouve la position d'index d'un élément dans un tableau trié. En C++, nous pouvons effectuer une recherche dichotomique en utilisant deux approches : itérative et récursive. Dans ce laboratoire, nous allons effectuer une opération de recherche dichotomique à l'aide d'un tableau dynamique.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/StandardLibraryGroup(["Standard Library"]) cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/FunctionsGroup(["Functions"]) cpp(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp/BasicsGroup -.-> cpp/data_types("Data Types") cpp/BasicsGroup -.-> cpp/arrays("Arrays") cpp/ControlFlowGroup -.-> cpp/conditions("Conditions") cpp/ControlFlowGroup -.-> cpp/while_loop("While Loop") cpp/FunctionsGroup -.-> cpp/function_parameters("Function Parameters") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") cpp/StandardLibraryGroup -.-> cpp/standard_containers("Standard Containers") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/data_types -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/arrays -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/conditions -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/while_loop -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/function_parameters -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/output -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/files -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/standard_containers -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} cpp/code_formatting -.-> lab-96172{{"Recherche dichotomique en CPP utilisant un tableau dynamique"}} end

Créer un nouveau fichier C++

Tout d'abord, nous créons un nouveau fichier C++ dans le répertoire ~/project nommé main.cpp.

touch ~/project/main.cpp

Inclure les fichiers d'en-tête

Ensuite, nous incluons les fichiers d'en-tête nécessaires - iostream, algorithm et vector.

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

using namespace std;

Créer un tableau dynamique et le remplir d'éléments

Nous créons un tableau dynamique d'entiers en utilisant la classe vector et le remplissons d'entiers triés.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Implémenter la fonction de recherche dichotomique

Ensuite, nous implémentons la fonction de recherche dichotomique qui recherche la position d'index d'un élément dans un tableau trié en utilisant l'approche itérative.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Appeler la fonction de recherche dichotomique et afficher le résultat

Enfin, nous appelons la fonction de recherche dichotomique avec un élément à rechercher et affichons le résultat dans la console.

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element not found!" << endl;
} else {
    cout << "Element found at index " << result << endl;
}

Compiler et exécuter le programme

Compilez et exécutez le programme dans le terminal en exécutant la commande suivante :

g++ main.cpp -o main &&./main

Code final

Voici le code complet du fichier main.cpp :

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

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element not found!" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }

    return 0;
}

Récapitulatif

Dans ce laboratoire, nous avons appris à effectuer une recherche dichotomique à l'aide d'un tableau dynamique en C++. Nous avons utilisé l'approche itérative et avons implémenté une fonction de recherche dichotomique pour rechercher la position d'index d'un élément dans un tableau trié. Nous avons également appris à créer un tableau dynamique à l'aide de la classe vector en C++.