Exercice : Tableaux triés

Exercice : Tableaux triés#

Dans le TP8, nous avons vu comment trier un tableau. Certaines opérations peuvent être réalisées de manière bien plus efficace sur un tableau déjà trié. Dans cet exercice vous allez explorer deux de ces opérations.

En général, la recherche d’une valeur dans un tableau prend un temps linéaire. En revanche, si le tableau est trié, elle peut être réalisée de manière plus efficace. En effet, au lieu de comparer séquentiellement la valeur recherchée à toutes les valeurs, il est possible, en la comparant uniquement à la valeur centrale, de décider si la valeur recherchée est située dans la première moitiée du tableau ou bien dans la seconde.

Définissez une fonction récursive qui recherche une valeur dans un tableau; elle prendra en paramètre un tableau trié, la valeur à rechercher, ainsi que les indices de début et de fin de la portion de tableau dans laquelle chercher. Cette fonction devra déterminer dans quelle moitié du tableau se trouve la valeur à chercher et s’appeler récursivement pour effectuer cette recherche. Elle renverra la position à laquelle la valeur à été trouvée ou -1 si la valeur n’est pas dans le tableau.

Réflechissez bien aux cas d’arrêt possibles et testez votre fonction en profondeur afin de vous assurez qu’elle est correcte.
```
int recherche(int T[], int val, int debut, int fin);
```
BEGIN SOLUTION
```
int recherche(int T[], int val, int debut, int fin) {
    if (fin - debut < 0)
        return -1;
    int milieu = (debut + fin) / 2;
    if (T[milieu] == val)
        return milieu;
    else if (T[milieu] > val)
        return recherche(T, val, debut, milieu - 1);
    else
        return recherche(T, val, milieu + 1, fin);
}
```
END SOLUTION
La recherche des valeurs communes entre deux tableaux est elle aussi une opération qui peut-être implémentée de manière efficace lorsque ceux-ci sont triés.

Définissez une fonction qui prend en paramètre deux tableaux ainsi que leurs tailles et qui supprime du premier tableau tous les éléments qui sont aussi présents dans le second. (la supression se faisant en décalant toutes la valeurs suivantes d’une position vers le début du tableau) La fonction renverra le nombre d’éléments présents dans le premier tableau une fois les suppressions effectuées.

Il est possible de réaliser cette opération en effectuant un seul parcours sur les deux tableaux. Réfléchissez bien aux détails de votre parcours, en n’oubliant notamment pas qu’une même valeur peut-être présente plusieurs fois dans un tableau.
```
int filtre(int T1[], int n1, int T2, int n2);
```
BEGIN SOLUTION
```
int filtre(int T1[], int n1, int T2, int n2) {
    int i1 = 0, i2 = 0;
    int r = 0;
    while (i1 < n1 && i2 < n2) {
        if (T1[i1] == T2[i2]) {
            i1++;
            continue;
        }
        T1[r] = T1[i1];
        i1++; r++;
        if (i1 == n1)
            break;
        while (T1[i1] > T2[i2])
            i2++;
    }
    while (i1 < n1) {
        T1[r] = T1[i1];
        i1++; r++;
    }

}
```
END SOLUTION