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;
} |
Partager