C Recherche dichotomique

Citation:

Envoyé par Akrramo

Code:

1
2
3
4
5
6
7
8
9
10
   printf ("Entrer la dimension du tableau");
   scanf ("%d", &n);
   for (i = 0; i < n; i++)
   {
      printf ("tb[%d]", i);
      scanf ("%d", &tb[i]);
   }
   printf ("Saisir une valeur a rechercher");
   scanf ("%d", &val);
   max = n;

Pour tester un algorithme de recherche dichotomique, tu n'as pas besoin de ce bazar (toujours limiter les opérations manuelles, dans un programme de test, elles sont sources d'erreur). De plus, rien ne garantit que le tableau soit trié...

Toujours aller au plus simple.

Définir un tableau trié

Code:

int tab[] = {-3, -1, 0, 2, 5, 7};

faire une recherche systématique, par exemple entre -5 et +10 :

Code:

1
2
3
4
5
6
7
8
9
 
for (i = -5, i <= 10, i++)
{
   int trouve = chercher (tab, i);
   if (trouve != -1)
   {
      printf ("%d\n", tab[trouve]);
   }
}

Ce qui donne :

Code:

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
 
#include<stdio.h>
 
static int G_count;
 
static int chercher (int const tab[], size_t n, int val)
{
#if 1
/* recherche lineaire pour tester le test */
   int ndx = -1;
   size_t i;
   for (i = 0; ndx == -1 && i < n; i++)
   {
      if (tab[i] == val)
      {
         ndx = i;
 
         /* debug */
         G_count += i;
      }
   }
   return ndx;
#endif
 
/* a toi d'ecrire le code 'dichotomique' */
}
 
static void afficher (int const tab[], size_t n)
{
   size_t i;
   for (i = 0; i < n; i++)
   {
      printf ("%4d", tab[i]);
   }
   printf ("\n");
}
 
int main (void)
{
   int tab[] = { -3, -1, 0, 2, 5, 7 };
   size_t const n = sizeof tab / sizeof *tab;
 
   afficher (tab, n);
 
   {
      int i;
      for (i = -5; i <= 10; i++)
      {
         int trouve = chercher (tab, n, i);
         if (trouve != -1)
         {
            printf ("[%d] = %4d\n", trouve, tab[trouve]);
         }
      }
      printf ("\n");
   }
 
   printf ("%d iterations\n", G_count);
 
   return 0;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
  -3  -1   0   2   5   7
[0] =   -3
[1] =   -1
[2] =    0
[3] =    2
[4] =    5
[5] =    7
 
15 iterations
 
Process returned 0 (0x0)   execution time : 0.025 s
Press any key to continue.

Maintenant, tu peux te concentrer sur la fonction 'chercher' pour faire baisser ce nombre d'itérations.