Recherche dichotomique en C pour insertion

Version imprimable

Bonjour je cherche une solution pour mon programme c:
je n'arrive pas à trouver la position d'insertion d'un chiffre dans un tableau rangé dans un ordre croissant à l aide d une recherche dichotomique.

voici mon code:
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 #include <stdio.h> int rech(int n,int x[10]){ int g=0,pos=0; int d=10; int trouve=0; while(g<d && trouve==0) { if(n>=x[((g+d)/2)]) { g=((g+d)/2)+1; printf("gauche %d \n",g); }else if(n<x[((g+d)/2)]){ d=((g+d)/2)-1; printf("droit %d \n",d); } printf("milieu %d\n",(g+d)/2); } return(pos); } int main(){ int tab[10] = {1, 3, 6, 15, 18, 19, 22, 24, 24, 25} ; int n,x; printf("entrez votre nombre \n"); scanf("%d",&n); x=rech(n,tab); printf("les resultat est :%d \n",x); }
si vous pouviez me donner quelques pistes car je suis un peu perdu dans mon si petit algo :'(

Merci

27/02/2009, 12h47
Obsidian
À vue de nez :
Citation:
Envoyé par G4uthier

Code:

1 2 3 4 5 6 7 8 9 10 11 12 #include <stdio.h> if(n>=x[((g+d)/2)]) { g=((g+d)/2)+1; printf("gauche %d \n",g); }else if(n<x[((g+d)/2)]){ d=((g+d)/2)-1; printf("droit %d \n",d); }
Ton nombre est toujours soit supérieur ou égal, soit inférieur. Il faut partir d'un côté ou de l'autre, seulement si ton nombre est supérieur ou inférieur, puisque le cas qui t'intéresse et doit provoquer l'arrêt de la boucle est précisément celui où il est égal.

D'autre part, tu utilises une variable « trouve », mais tu la passes jamais à un.
27/02/2009, 14h17
Médinoc

D'un autre côté, si une recherche dichotomique est utile en consultation, il ne faut pas oublier qu'elle ne suffira pas à réduire l'ordre de complexité de ton insertion: À cause du décalage causé par une insertion dans un tableau, ton insertion sera toujours en O(n).
27/02/2009, 18h28
G4uthier

Citation:

Envoyé par Médinoc

D'un autre côté, si une recherche dichotomique est utile en consultation, il ne faut pas oublier qu'elle ne suffira pas à réduire l'ordre de complexité de ton insertion: À cause du décalage causé par une insertion dans un tableau, ton insertion sera toujours en O(n).

oui je sais mais le but de mon exercice est de privilégier la recherche à l'insertion .

Merci pour ta réponse j'essaie ta solution en rentrant :)

Salut,

Une fois j'avais un truc comme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
 
 size_t dicosearch( int * T , size_t size  ,  int v  )
 { 
     if ( size == 0 ) return (size_t)  -1 ;
     size_t  hi = size -1 ;
     size_t  lo = 0 ;
     size_t  mid ;
     while( lo <= hi )
      { mid = ( hi + lo ) / 2 ;
	if( v  <  T [mid] ) hi = mid-1 ;
	else
	if( v >  T [mid] ) lo = mid+1 ;
	else
	return mid ;
      }
     return (size_t) -1   ;
 }

Ca ne marche que sur des données déjà triées.

Citation:

Envoyé par dj.motte

Une fois j'avais un truc comme :

Ne passe pas ce test (comportement indéfini)

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
 
#include <stddef.h>
 
size_t dicosearch (int *T, size_t size, int v)
{
   if (size == 0)
      return (size_t) - 1;
   size_t hi = size - 1;
   size_t lo = 0;
   size_t mid;
   while (lo <= hi)
   {
      mid = (hi + lo) / 2;
      if (v < T[mid])
         hi = mid - 1;
      else if (v > T[mid])
         lo = mid + 1;
      else
         return mid;
   }
   return (size_t) - 1;
}
 
#ifdef TEST
#include <stdio.h>
#include <assert.h>
 
int main (void)
{
#define N(a) (sizeof(a)/sizeof*(a))
   {
      int a[] = { 1 };
      assert (dicosearch (a, N (a), 1) == 0);
      assert (dicosearch (a, N (a), 0) == (size_t) - 1);
   }
 
 
   puts("P A S S E D");
   return 0;
}
#endif

Un instrumentation basique du code montre qu'il y a débordement du tableau :

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
 
#include <stddef.h>
#include <assert.h>
 
size_t dicosearch (int *T, size_t size, int v)
{
   if (size == 0)
      return (size_t) - 1;
   size_t hi = size - 1;
   size_t lo = 0;
   size_t mid;
   while (lo <= hi)
   {
      mid = (hi + lo) / 2;
      assert (mid < size);
      if (v < T[mid])
         hi = mid - 1;
      else if (v > T[mid])
         lo = mid + 1;
      else
         return mid;
   }
   return (size_t) - 1;
}

Valeurs de 'mid' :

Code:

1
2
3
4
5
6
7
8
9
10
11
 
mid          = 0
mid          = 0
mid          = 2147483647
Assertion failed: mid < size, file C:\dev\hello\main.c, line 17
 
This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
 
Process returned 3 (0x3)   execution time : 4.538 s
Press any key to continue.

Ceci fonctionne :

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
62
63
64
65
 
#include "ed/inc/prt.h"
 
#include <assert.h>
#include <stddef.h>
 
size_t dicosearch (int *T, size_t size, int v)
{
   if (T == NULL || size == 0)
      return (size_t) - 1;
   size_t hi = size - 1;
   size_t lo = 0;
   size_t mid = (hi + lo) / 2;
   while (mid < size && lo <= hi)
   {
      assert (mid < size);
      if (v < T[mid])
         hi = mid - 1;
      else if (v > T[mid])
         lo = mid + 1;
      else
         return mid;
      mid = (hi + lo) / 2;
   }
 
   return (size_t) - 1;
}
 
#ifdef TEST
#include <stdio.h>
#include <assert.h>
 
int main (void)
{
   assert (dicosearch (NULL, 1, 1) == (size_t) - 1);
   assert (dicosearch (1, 0, 1) == (size_t) - 1);
#define N(a) (sizeof(a)/sizeof*(a))
   {
      int a[] = { 1 };
      assert (dicosearch (a, N (a), 1) == 0);
      assert (dicosearch (a, N (a), 0) == (size_t) - 1);
      assert (dicosearch (a, N (a), -1) == (size_t) - 1);
   }
 
   {
      int a[] = { 1, 2 };
      assert (dicosearch (a, N (a), 1) == 0);
      assert (dicosearch (a, N (a), 2) == 1);
      assert (dicosearch (a, N (a), 0) == (size_t) - 1);
      assert (dicosearch (a, N (a), -1) == (size_t) - 1);
   }
 
   {
      int a[] = { 1, 2, 3 };
      assert (dicosearch (a, N (a), 1) == 0);
      assert (dicosearch (a, N (a), 2) == 1);
      assert (dicosearch (a, N (a), 3) == 2);
      assert (dicosearch (a, N (a), 0) == (size_t) - 1);
      assert (dicosearch (a, N (a), -1) == (size_t) - 1);
   }
 
   puts ("P A S S E D");
   return 0;
}
#endif