19
Recherche par dichotomie
- #include <stdlib.h>
- #include <stdio.h>
- static void print( int tab[], const int siz ) {
- int i;
- for ( i=0; i < siz; i++ )
- printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
- }
- int search( int val, int tab[], const int siz ) {
- int l = 0, r = siz-1;
- int i;
- while ( l <= r ) {
- i = (l + r) / 2;
- if (tab[ i ] == val)
- return i;
- if ( tab[ i ] < val )
- l = i+1;
- else
- r = i-1;
- }
- return -i - 1; /* return where it could be inserted - 1 */
- }
- int main() {
- int tab[ ] = { -4, -3, 0, 1, 2, 3, 6, 7, 9, 10 };
- int siz = sizeof (tab) / sizeof (int);
- int val;
- print( tab, siz );
- printf("Enter a number to search, to insert or ^Z|^D.\n");
- for( ;; ) {
- printf("\n? ");
- switch( scanf( "%d", &val ) ) {
- case -1:
- exit(0);
- case 1:
- printf(" = %d", search( val, tab, siz ) );
- break;
- default:
- scanf( "%*s" ); /* swallow bad input */
- break;
- }
- }
- }
Commentaires