Recherche de la première occurrence dans un tableau trié

Introduction

Dans ce laboratoire, nous allons apprendre à trouver la première occurrence d'un nombre donné dans un tableau trié en utilisant une recherche dichotomique modifiée en C++.

Le fichier de code C++

Tout d'abord, créons un fichier de code C++ nommé main.cpp dans le répertoire ~/project à l'aide de l'éditeur de texte touch.

touch ~/project/main.cpp

Inclure les en-têtes nécessaires dans le code

Nous devons inclure les fichiers d'en-tête C++ nécessaires dans notre programme. Copiez et collez le code suivant dans votre fichier main.cpp.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Créer une fonction pour trouver la première occurrence d'un élément

Nous allons créer une fonction appelée first() qui prend un tableau, son indice inférieur, son indice supérieur et l'élément à rechercher en entrée. La fonction retournera l'indice de la première occurrence de l'élément. Incluez le code suivant dans le fichier main.cpp.

int first(int a[], int l, int h, int b)
{
    int res = -1;
    while (l <= h)
    {
        int m = (l + h) / 2;
        if (a[m] == b)
        {
            res = m;
            h = m - 1;
        }
        else if (a[m] > b)
        {
            h = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return res;
}

Ici, nous avons utilisé la recherche dichotomique pour trouver la première occurrence de l'élément. Nous avons initialisé la variable res à -1 pour gérer le cas où l'élément n'est pas présent dans le tableau. Si l'élément du milieu est égal à l'élément que nous cherchons, nous stockons l'indice de l'élément du milieu dans res et mettons à jour l'indice supérieur à m-1 car nous cherchons la première occurrence de l'élément. Si l'élément du milieu est supérieur à l'élément que nous cherchons, nous mettons à jour l'indice supérieur à m-1, et s'il est inférieur à l'élément, nous mettons à jour l'indice inférieur à m+1.

Implémenter la fonction principale

Dans la fonction principale, nous allons créer un tableau, appeler la fonction first créée à l'étape 3 avec les arguments appropriés et afficher le résultat à la console. Copiez et collez le code ci-dessous dans la fonction main.

int main()
{
    int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};

    int n = sizeof(a) / sizeof(a[0]);

    int k = 4; //l'élément pour lequel on veut trouver l'indice de la première occurrence

    int f = first(a, 0, n - 1, k);

    if(f==-1)
    {
        cout << "Element not found\n";
    }
    else
    {
        cout << "The index of the first occurrence of " << k << " is: " << f << endl;
    }

    return 0;
}

Ici, nous avons déclaré un tableau d'entiers nommé a et l'initialisé avec des valeurs d'entiers triées. Nous avons également calculé le nombre d'éléments dans le tableau à l'aide de l'opérateur sizeof. Nous avons ensuite appelé la fonction first() avec les arguments appropriés et affiché le résultat.

Compiler et exécuter le code C++

Maintenant, nous pouvons compiler et exécuter le code C++ à l'aide des commandes suivantes.

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

Si tout se passe bien, la sortie sera The index of the first occurrence of 4 is: 3.

Résumé

Dans ce laboratoire, nous avons appris à trouver la première occurrence d'un nombre donné dans un tableau trié en utilisant une recherche dichotomique modifiée en C++. Nous avons créé une fonction first() pour implémenter l'algorithme.