fig2_9.c

weis的数据结构的实现方法很经典很强大

#include <stdio.h>

typedef int ElementType;
#define NotFound (-1)

/* START: fig2_9.txt */
        int
        BinarySearch( const ElementType A[ ], ElementType X, int N )
        {
            int Low, Mid, High;

/* 1*/      Low = 0; High = N - 1;
/* 2*/      while( Low <= High )
            {
/* 3*/          Mid = ( Low + High ) / 2;
/* 4*/          if( A[ Mid ] < X )
/* 5*/              Low = Mid + 1;
                else
/* 6*/          if( A[ Mid ] > X )
/* 7*/              High = Mid - 1;
                else
/* 8*/              return Mid;  /* Found */
            }
/* 9*/      return NotFound;     /* NotFound is defined as -1 */
        }
/* END */

main( )
{
    static int A[ ] = { 1, 3, 5, 7, 9, 13, 15 };
    const int SizeofA = sizeof( A ) / sizeof( A[ 0 ] );
    int i;

    for( i = 0; i < 20; i++ )
        printf( "BinarySearch of %d returns %d\n",
                 i, BinarySearch( A, i, SizeofA ) );
    return 0;
}