27

Search by dichotomy

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. static void print( int tab[], const int siz ) {
  5.     int i;
  6.     for ( i=0; i < siz; i++ )
  7.         printf((i < siz-1) ? "%d, " : "%d\n", tab[ i ]);
  8. }
  9.  
  10. int search( int val, int tab[], const int siz ) {
  11.     int l = 0, r = siz-1;
  12.     int i;
  13.  
  14.     while ( l <= r ) {
  15.         i = (l + r) / 2;
  16.         if (tab[ i ] == val)
  17.             return i;
  18.         if ( tab[ i ] < val )
  19.             l = i+1;
  20.         else
  21.             r = i-1;
  22.     }
  23.     return -i - 1;  /* return where it could be inserted - 1 */
  24. }
  25.  
  26. int main() {
  27.     int tab[ ] = { -4, -3, 0, 1, 2, 3, 6, 7, 9, 10 };
  28.     int siz = sizeof (tab) / sizeof (int);
  29.     int val;
  30.  
  31.     print( tab, siz );
  32.     printf("Enter a number to search, to insert or ^Z|^D.\n");
  33.     for( ;; ) {
  34.         printf("\n? ");
  35.         switch( scanf( "%d", &val ) ) {
  36.             case -1:
  37.                 exit(0);
  38.             case 1:
  39.                 printf(" = %d", search( val, tab, siz ) );
  40.                 break;
  41.             default:
  42.                 scanf( "%*s" ); /* swallow bad input */
  43.                 break;
  44.         }
  45.     }
  46. }

Comments

Your comment:
[p] [b] [i] [u] [s] [quote] [pre] [br] [code] [url] [email] strip help 2000

Enter a maximum of 2000 characters.
Improve the presentation of your text with the following formatting tags:
[p]paragraph[/p], [b]bold[/b], [i]italics[/i], [u]underline[/u], [s]strike[/s], [quote]citation[/quote], [pre]as is[/pre], [br]line break,
[url]http://www.izend.org[/url], [url=http://www.izend.org]site[/url], [email]izend@izend.org[/email], [email=izend@izend.org]izend[/email],
[code]command[/code], [code=language]source code in c, java, php, html, javascript, xml, css, sql, bash, dos, make, etc.[/code].