Recherche dichotomique d'un élément dans un tableau ordonné

On n'a pas appris le C au même endroit. As-tu essayé de compiler ton code?

Où as-tu pris ce code?

Dans la fonction view, pourquoi changes tu la valeur de inf et sup?

Avec un peu d'imagination, ça pourrait ressembler à une recherche dichotomique.

Il y a plusieurs implémentations itératives de cet algorithme.

Fais une recherche sur le web.

P.S. Une recherche dichotomique se fait sur untableau ordonné (c'est le cas ici)

p'tet qu'avant de te lancer dans cet exercice, tu devrais corriger (comprendre) celui-ci https://forums.commentcamarche.net/forum/affich-38004912-exercice-sur-les-pointeurs#dernier

Plusieurs erreurs pour si peu de code:
Ce n'est pas la bonne façon de déclarer un enum ni un typedef.
Il existe le type bool dans <stdbool.h>
Les définitions de enum et de tableaux se font avec { } au lieu de ( )
Tu utilises *elt alors que elt n'a pas été défini comme pointeur (voir le lien de Whismeril).
Dans view(), la boucle va de 5 à 32 au lieu de inf aà sup. Ça me laisse croire à une incompréhension du passage des paramètres.

Tu n'afficheras pas ce que tu crois afficher.

Dans fun(), les appels récursifs ne retournent rien.
Et l'algo lui-même n'est pas correct.

edit: il fonctionne mais oblige à descendre à un intervalle de un seul élément.

Bonjour,

Remarques préliminaires

Merci de partager à l'avenir tes extraits de code comme expliqué ici et surtout à l'indenter correctement, ça t'évitera des erreurs de programmation. Je te conseille aussi d'ouvrir et fermer systématiquement des paires d'accolades après chaque if/else/for/while et de revenir à la ligne après chaque { et chaque }, ça rendra ton code plus lisible et t'évitera probablement des erreurs de programmation sur des projets plus longs.

Ensuite, ce serait pas mal aussi d'utiliser un titre de discussion moins vague et d'expliquer l'objectif de ton programme.

Retours sur le code

La ligne 3 est mal écrite :

• comme souligné par Pierrot #3, le type bool s'utilise ainsi :

#include <stdbool.h>

int main() {
    bool b1 = true;
    bool b2 = true;
    return 0;
}

La ligne 14 est "confusante" car si j'ai bien compris ton programme, inf est toujours sensé être inférieur ou égale à sup et donc j'aurais plutôt distingué :

if (inf < sup) {
    // Continuer à resserrer [inf, sup]
} else if (inf == sup) {
    // Regarder si elt est bien ici
} else {
    // Erreur, on ne devrait être dans ce cas
}

La ligne 15 me paraît très suspecte.

• Si tu veux faire un test (ce qui est à mon avis le bug que tu recherches et qui t'amène ici, soit dit en passant), tu dois écrire : 

if (vec[med] == *elt)

• Actuellement, tu fais une affectation de *elt dans vec[med]. Le résultat de cette opération est la valeur assignée dans vec[med]. Si cette valeur est non nulle alors le test est vrai, sinon il est faux. Cela signifie qu'à chaque fois que tu fais ce test, tu modifies le contenu de vec. Je doute que c'est ce que tu voulais écrire. Comme écrire = au lieu de == est vite arrivé, normalement ton compilateur te prévient. Dans les cas où tu veux bel est bien faire le test + l'affectation, le compilateur attend que tu insistes dessus en doublant les parenthèses du if. Dans ton cas, cela reviendrait à écrire :

if ((vec[med] = *elt))

Comment afficher une partie d'un tableau

Je vais la reformuler plus précisément en : comment afficher un slice de tableau tab de type int *, de l'index i (inclu) à l'indice j (exclu).

#include <stdio.h>

void print_tab(
    int * tab,
    size_t num_elements,
    size_t i,
    size_t j
) {
    printf("[");
    for (size_t k = i; k < j; k++) {
        printf(" %d", tab[k]);
    }    
    printf(" ]\n");
}
    
int main() {
    int tab[] = {10, 20, 30, 40, 50, 60};
    size_t num_elements = sizeof(tab) / sizeof(int);
    print_tab(tab, num_elements, 0, 6);
    // [ 10 20 30 40 50 60 ]
    print_tab(tab, num_elements, 2, 5);
    // [ 30 40 50 ]
    print_tab(tab, num_elements, 2, 3);
    // [ 30 ]
    print_tab(tab, num_elements, 2, 2);
    // [ ]
    print_tab(tab, num_elements, 2, 1);
    // [ ]
    return 0;      
}

Version itérative

Dans les grandes lignes, il faut remplacer ton appel récursif et utiliser une boucle while dont tu devras quitter quand un critère d'arrêt sera atteint.

La première chose à faire est donc de comprendre quels sont ces critères d'arrêts, et comment garantir qu'à chaque tour de boucle, tu réduis strictement ton espace de recherche.

Comme ici ton but est de resserrer tes indices inf et sup pour trouver med donc il y a de bonnes chances que ton critère d'arrêt consiste à vérifier si inf == sup et t'assurer qu'à chaque tour de boucle, soit inf se rapproche de sup, soit sup se rapproche de inf.

Bonne chance

@mamiemando, je me demande si Steve17_17 a compris comment calculer la longueur d'un tableau avec la formule:
    num_elements = sizeof(tab) / sizeof(tab[0]);
Cette variable n'est pas utilisée dans la fonction print_tab().
Je suppose que tu lui a laissé le soin de calculer par lui-même si les bornes i et j étaient correctes.
Mathématiquement: 0 <= i < j <= num_elements
Une chose qui peut embêter le débutant qui cherche une implémentation est le fait qu'il y a deux variantes possibles:
Premièrement, inf est l'indice du premier élément et sup est l'indice du dernier élément.
Deuxièmement, inf est toujours l'indice du premier, mais sup est l'indice de l'élément suivant du dernier.
Dans cette seconde variante, sup - inf est la longueur du sous-tableau à chercher.
Le test de resserrement et d'ajustement de inf ou sup par rapport à med est légèrement différent.
L'idée de resserrer autour de l'élément cherché est correcte mais pas forcément la plus efficace.
Je donne un exemple simple avec le tableau suivant:
[10, 20, 30, 40, 50, 60, 70]
avec la seconde variante, inf = 0 et sup = 7 et je recherche la valeur 40.
Alors, med = (inf + sup) / 2 = (0 + 7) / 2 = 3
Et justement 40 se trouve à l'indice 3. Je la trouve donc à la première récursion (ou itération)
L'idée est de tester les bornes et évaluer la valeur de med tout de suite après.
Si inf > sup ou inf >= sup suivant la variante, on n'a pas trouvé.
Sinon, on calcule tout de suite la valeur de med et on teste tout de suitte si la valeur à cette position est la valeur cherchée.
Si c'est le cas, on sort avec true ou l'indice où se trouve la valeur cherchée.
Sinon on cherche dans ce qui précède ou ce qui suit suivant que cette valeur vienne avant ou après celle de la position med.
Première variante: fun(tab, inf, med-1) ou fun(tab, med+1, sup)
Seconde variante: fun(tab, inf, med) ou fun(tab, med+1, sup)

D'accord grand merci, j'ai pris note