bonjour,

J'ai fait une petite fonction qui recherche une valeur dans un tableau trié : si la valeur est présente plusieurs fois dans le tableau, cette fonction doit retourner le premier élément du tableau.

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
static int find_firstElement(int val, int tab[], int len){
 
    int sup, inf, demi;
 
    //On définit les bornes de la partie du tableau à considérer
    inf = 0;
    sup = len - 1;
    if(sup < 1){
        return -1;
    }
 
    int i;
    printf("Tab[] =");
    for(i=0; i<len; i++){
        printf(" %i", tab[i]);
    }
    printf("\n");
 
 
    // ****************************
    while(1){
        demi = (sup + inf)/2;
 
        if(tab[demi] > val){
            sup = demi - 1;
            if(tab[sup] < val){
                return -1;
            }
 
        } else if(tab[demi] < val){
            inf = demi + 1;
            if(tab[inf] > val){
                return -1;
            }
 
        } else {
            sup = demi; // balise supérieure trouvée
            // => il reste a trouver le premier element de la liste
            break;
        }
    }
    printf("step1 : inf = %i, sup = %i\n", inf, sup);
 
 
    // ****************************
    //int myTab1[] = {0,1,1,1,2,3,5,7};
    while(1){
        demi = (sup + inf)/2;
 
        if(tab[demi] >= val){
            // Normalement tab[demi] ne devrait jamais etre supérieur a val
            // (mais on fait quand meme le test '<=' au lieu de '==' par sécurité
 
            sup = demi;
            printf("step2a : inf = %i, sup = %i\n", inf, sup);
 
        } else {
            inf = demi + 1;
            printf("step2d : inf = %i, sup = %i\n", inf, sup);
 
            if(inf >= sup){
                printf("step2e : inf = %i, sup = %i\n", inf, sup);
                return sup; // premier element trouvé
            }
        }
    }
 
 
    return -1;
}
 
 
int main()
{
    int index;
    int myTab1[] = {0,1,1,1,2,3,5,7};
    int myTab2[] = {0,0,1,1,1,2,3,5,7};
    int myTab3[] = {0,1,1,2,2,3,5,7};
    int myTab4[] = {0,1,1,1,2,2,3,5,7};
    int myTab5[] = {0,0,0,0,1,2,2,3,5,7};
    int myTab6[] = {0,0,0,0,2,2,3,5,7};
 
 
    // le tableau doit etre trié par odre croissant
    index = find_firstElement(1, myTab1, sizeof(myTab1) / sizeof(*myTab1));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab2, sizeof(myTab2) / sizeof(*myTab2));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab3, sizeof(myTab3) / sizeof(*myTab3));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab4, sizeof(myTab4) / sizeof(*myTab4));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab5, sizeof(myTab5) / sizeof(*myTab5));
    printf("result = %i\n\n", index);
 
    index = find_firstElement(1, myTab6, sizeof(myTab6) / sizeof(*myTab6));
    printf("result = %i\n\n", index);
 
    return 0;
}
ça semble fonctionner mais comment faire pour en etre sure ?
voyez-vous des améliorations afin d'optimiser la rapidité de l'algo ?

merci d'avance