Discussion :

[G4uthier]

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 :

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
#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

[Obsidian]

À vue de nez :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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).

[G4uthier]

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

[dj.motte]

Salut,

Une fois j'avais un truc comme :

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
 
 
 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.

[Emmanuel Delahaye]

Une fois j'avais un truc comme :

Ne passe pas ce test (comportement indéfini)

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
 
#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 :

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
 
#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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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
 
#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